中科院基于短語的統(tǒng)計機器翻譯系統(tǒng).pdf

基于短語的統(tǒng)計機器翻譯系統(tǒng)基于短語的統(tǒng)計機器翻譯系統(tǒng) 絲路 絲路 1 0 版 版 SilkRoad V1 0 設(shè)計與使用說明設(shè)計與使用說明 中科院計算所 中科院自動化所 中科院軟件所 廈門大學(xué) 哈爾濱工業(yè)大學(xué) 2006 年 10 月 2 引 言引 言 絲路 SilkRoad 是一個基于短語的漢英統(tǒng)計機器翻譯系統(tǒng) 該系統(tǒng)由中國的五家 研究機構(gòu)和高校聯(lián)合開發(fā) 中科院計算所 中科院自動化所 中科院軟件所 廈門大學(xué) 哈 爾濱工業(yè)大學(xué) 并在 2006 年中國第二屆統(tǒng)計機器翻譯研討會上發(fā)布 供國內(nèi)外研究者共享 使用 聯(lián)合開發(fā)單位希望通過這個系統(tǒng)的發(fā)布 使更多的研究者能夠更快 更容易地加入到 統(tǒng)計機器翻譯研究中來 推動國內(nèi)統(tǒng)計機器翻譯的迅速發(fā)展 本文檔給出了 絲路 1 0 版 SilkRoad V1 0 的設(shè)計與使用說明 系統(tǒng)采用了目前主流的基于短語的統(tǒng)計機器翻譯方法 在系統(tǒng)實現(xiàn)上充分利用了國際上 目前已有的一些資源 包括一些開放源代碼工具和一些可以公開獲得授權(quán)的工具 在此基礎(chǔ) 上 聯(lián)合開發(fā)單位分工協(xié)作 補充完成了翻譯系統(tǒng)中尚不能公開獲得的關(guān)鍵模塊 包括語料 庫預(yù)處理 后處理模塊 詞語對齊后處理模塊 短語抽取模塊 解碼器模塊等 本文檔主要 介紹系統(tǒng)的整體設(shè)計以及這些新開發(fā)模塊的實現(xiàn)原理和使用說明 聯(lián)合開發(fā)單位的具體分工如下 中科院計算所 總體設(shè)計 語言模型接口設(shè)計和 駱駝 CAMEL 解碼器 中科院軟件所 語料的預(yù)處理 后處理模塊 仙人掌 中科院自動化所 詞語對齊后處理模塊 樓蘭 和短語抽取模塊 胡楊 廈門大學(xué) 商隊 Caravan 解碼器 哈爾濱工業(yè)大學(xué) 綠洲 Oasis 解碼器 解碼器是統(tǒng)計翻譯系統(tǒng)的核心模塊 有三家單位分別開發(fā)了自己的解碼器模塊 這三個 解碼器是相互獨立的 用戶可以選擇使用其中任何一個解碼器來完成翻譯過程 此外 該系統(tǒng)在實現(xiàn)時采用了 863 中文信息處理與智能人機接口評測 2005 年漢英機 器翻譯評測的數(shù)據(jù)集 包括訓(xùn)練集 開發(fā)集和測試集 這些數(shù)據(jù)可以通過 ChineseLDC 獲得 研究目的授權(quán) 3 目錄目錄 目錄目錄 3 1 絲路 系統(tǒng)設(shè)計概述 絲路 系統(tǒng)設(shè)計概述 4 1 1 基于短語的統(tǒng)計機器翻譯模型 4 1 2 系統(tǒng)流程 4 1 3 模塊劃分 6 1 4 已有資源和工具簡介 7 1 5 數(shù)據(jù)格式定義 8 2 訓(xùn)練模塊設(shè)計與使用訓(xùn)練模塊設(shè)計與使用 17 2 1 訓(xùn)練語料預(yù)處理 17 2 2 詞語對齊 19 2 3 短語抽取 22 3 解碼模塊設(shè)計與使用解碼模塊設(shè)計與使用 27 3 1 輸入預(yù)處理 27 3 2 語言模型接口使用說明 27 3 3 駱駝 CAMEL 解碼器 29 3 4 商隊 Caravan 解碼器 42 3 5 綠洲 Oasis 解碼器 45 3 6 輸出后處理 51 4 評測工具簡介評測工具簡介 52 4 1 評價指標(biāo) 52 4 2 使用說明 53 5 參考文獻(xiàn)參考文獻(xiàn) 54 4 1 絲路 系統(tǒng)設(shè)計概述 絲路 系統(tǒng)設(shè)計概述 本章主要介紹 絲路 漢英統(tǒng)計機器翻譯系統(tǒng)的總體設(shè)計 1 1 基于短語的統(tǒng)計機器翻譯模型基于短語的統(tǒng)計機器翻譯模型 基于短語的統(tǒng)計機器翻譯 Koehn et al 2003 Zens et al 2002 Koehn 2004 以短語作 為翻譯的基本單位 對于一個漢語句子 翻譯系統(tǒng)將其劃分為多個連續(xù)的詞語串 即所謂的 短語 然后將每一個漢語短語翻譯為英語短語 最后將產(chǎn)生的英語短語進(jìn)行順序調(diào)整 并輸出譯文 請參考圖 1 的例子 圖 1 基于短語的統(tǒng)計機器翻譯過程示例 1 2 系統(tǒng)流程系統(tǒng)流程 絲路 系統(tǒng)包含以下 個主要部分 短語翻譯模型的訓(xùn)練 語言模型的訓(xùn)練 解碼 翻譯結(jié)果的評價 下面以流程圖的形式分別介紹這 部分 1 2 1 短語翻譯模型的訓(xùn)練短語翻譯模型的訓(xùn)練 通過短語翻譯模型的訓(xùn)練 從漢英句子對齊的語料庫中學(xué)習(xí)到漢語短語到英語短語的翻 譯概率表 流程圖參見圖 2 原文 他 將 于 月 日 訪問 美國 短語劃分 他將 于 月 日 訪問美國 翻譯 He will on April 10 visit America 調(diào)整順序 He will visit America on April 10 5 圖 2 短語翻譯模型訓(xùn)練的流程 1 2 2 語言模型的訓(xùn)練語言模型的訓(xùn)練 在英語單語語料庫上訓(xùn)練得到英語的語言模型 流程圖參見圖 3 圖 3 語言模型訓(xùn)練的流程 1 2 3 解碼解碼 解碼器是系統(tǒng)的核心模塊 通過解碼 將一個輸入的漢語句子翻譯成英語句子 流程圖 參見圖 4 英語單語文本 語言模型訓(xùn)練 英語語言模型 訓(xùn)練語料庫 訓(xùn)練語料庫預(yù)處理 分詞的訓(xùn)練語料庫 詞語對齊 詞語對齊的語料庫 短語抽取 短語翻譯概率表 漢語切分工具 英語切分工具 語料庫格式轉(zhuǎn)換 規(guī)范的訓(xùn)練語料庫 6 圖 4 解碼的流程 1 2 4 翻譯結(jié)果的評價翻譯結(jié)果的評價 我們采用評價工具對系統(tǒng)的輸出結(jié)果進(jìn)行自動評價 流程圖參見圖 5 圖 5 評價的流程 1 3 模塊劃分模塊劃分 整個系統(tǒng)由以下模塊構(gòu)成 1 訓(xùn)練語料庫預(yù)處理模塊 2 漢語分詞工具 利用開源工具 ICTCLAS 3 英語分詞工具 將開源工具 tokenizeE perl tmpl 改寫為 C 代碼 4 詞語對齊模塊 利用開源工具 GIZA 獲得初始對齊 對其結(jié)果進(jìn)行后處理 5 短語抽取模塊 6 語言模型訓(xùn)練模塊 利用開源工具 SRI 7 語言模型應(yīng)用工具 利用開源工具 SRI 8 輸入預(yù)處理模塊 9 解碼模塊 輸出文本 結(jié)果數(shù)據(jù) 評價工具 評價結(jié)果 參考答案 輸入文本 測試數(shù)據(jù) 輸入預(yù)處理 規(guī)范輸入文本 解碼 中間輸出文本 輸出后處理 輸出文本 結(jié)果數(shù)據(jù) 短語翻譯概率表 英語語言模型 語言模型應(yīng)用工具 7 10 輸出后處理模塊 11 評價模塊 利用 863 評測工具 每個模塊都是一個可獨立執(zhí)行的文件 可以運行在 Windows 或者 Linux 等不同的平臺 上 模塊之間以文件作為接口 這些文件包括 1 訓(xùn)練語料庫 2 規(guī)范的訓(xùn)練語料庫 采用 GIZA 定義 3 分詞的訓(xùn)練語料庫 采用 GIZA 定義 4 詞語對齊的語料庫 5 短語翻譯概率表 6 語言模型 采用 SRI 定義 7 輸入文本 采用 863 評測定義 8 輸出文本 采用 863 評測定義 9 參考答案 采用 863 評測定義 10 評價結(jié)果 采用 863 評測定義 1 4 已有資源和工具簡介已有資源和工具簡介 從上面的介紹可以看到 這個系統(tǒng)相當(dāng)一部分的工作都可以利用已有的資源 這里對這 些資源作一個簡單介紹 1 4 1 漢語分詞工具漢語分詞工具 ICTCLAS 漢語詞法分析系統(tǒng)ICTCLAS是由中國科學(xué)院計算技術(shù)研究所自然語言處理課題組開發(fā) 的一套開放源代碼的漢語分詞和詞性標(biāo)注工具 可以在 中文自然語言處理開放平臺 上下 載 該平臺網(wǎng)址為 注意下載之前要使用真實信息注冊一個用戶名 1 4 2 詞語對齊模塊詞語對齊模塊 GIZA GIZA 是由 Och 等人在 1999 年 JHU 夏季討論班上開發(fā)的一個開放源代碼的統(tǒng)計機器翻 譯系統(tǒng) Egypt 的一部分 是一個 IBM 統(tǒng)計翻譯模型 Brown et al 1993 的訓(xùn)練工具 后來 Och 對它進(jìn)行了改進(jìn) 這就是 GIZA GIZA 的主頁是 GIZA 原來是在 linux 上運行的 有個中國人 網(wǎng)名 Blue Gene 把 GIZA 移植到了 Windows 的 Visual Studio C 7 0 平臺 下載地址是 關(guān)于 GIZA 的使用 中國科學(xué)院計算技術(shù)研究所的博士生劉洋寫了一份詳盡的報告 利用現(xiàn)有軟件構(gòu)建統(tǒng)計機器翻譯系統(tǒng) 這份報告介紹了如何搭建一個基于 IBM 模型的統(tǒng)計機器翻譯系統(tǒng) 主要采用的工具就 是 GIZA 當(dāng)然我們現(xiàn)在要做的是一個基于短語的系統(tǒng) 比 IBM 模型有了很大的改進(jìn) 1 4 3 英語分詞工具英語分詞工具 tokenizeE perl tmpl tokenizeE perl tmpl 是一個簡單的英語分詞工具 和 GIZA 一樣 都是 Egypt 系統(tǒng)的一部 分 完整的 Egypt 可以在以下網(wǎng)頁下載 http www clsp jhu edu ws99 projects mt toolkit 8 里面包含了這個英語分詞工具 我們將這個工具改寫為 C 代碼 由語料庫預(yù)處理模塊直接調(diào)用 1 4 4 語言模型工具語言模型工具 SRI SRILM 是 SRI 口語技術(shù)與研究實驗室 SRI Speech Technology and Research Laboratory 發(fā)布的開源的語言模型工具包 這個工具包包含一組 C 類庫 一組進(jìn)行語言模型訓(xùn)練和應(yīng) 用的可執(zhí)行程序 其它相關(guān)工具 SRILM 的主頁是 SRILM 的最新版本是 1 5 0 版 下載地址是 考慮到可移植性 訓(xùn)練出的語言模型數(shù)據(jù)采用 ARPA 標(biāo)準(zhǔn)格式 細(xì)節(jié)請參考 Jurafsky Align Intersect intersect e2f f2e Align Union union e2f f2e Heuristic Heuristic for english word e 0 en for chinese word f 0 fn if e aligned with f for each neighboring point e new f new if e new not aligned and f new not aligned and e new f new in Align Union add alignment point e new f new 算法 1 詞語對齊優(yōu)化算法 20 圖 6 生成 Heuristic 對齊結(jié)果的具體過程 21 2 2 3 使用說明使用說明 1 輸入 文件 Giza 雙向訓(xùn)練的對齊結(jié)果文件 從漢語到英語方向 從英語到漢語 方向 默認(rèn)文件為當(dāng)前目錄下 f2e giza alignment txt e2f giza alignment txt 參數(shù)選擇 在程序運行初始 可以選擇輸出 5 種不同的優(yōu)化結(jié)果作為參數(shù) a F2E 漢語到英語的對齊結(jié)果 b E2F 英語到漢語的對齊結(jié)果 c Union 兩個方向取并集 d Intersect 兩個方向取交集 e Heuristic 利用前面提到的 Och 的 Refined alignment 的思路 將交集點向 其周圍的 鄰居 進(jìn)行擴展 Och 2002 Koehn et al 2003 2 輸出 按照詞語對齊的語料庫的格式定義 以 xml 文件輸出 默認(rèn)文件為當(dāng)前目錄下 Alignment xml 3 注意事項 在進(jìn)入 Giza 訓(xùn)練之前 已將中文或英文大于 100 個詞的句對過濾 所以在該 模塊默認(rèn)的最大句長是 100 全局變量 MAX 在進(jìn)行參數(shù)選擇時 要按照提示中指定格式進(jìn)行輸入 要包含前面的代碼和具 體類別 如 5 Heuristic 在產(chǎn)生對齊結(jié)果的過程中 每處理 1000 句 屏幕顯示一個 具體細(xì)節(jié)詳見代碼中注釋 22 2 3 短語抽取 胡楊 短語抽取 胡楊 負(fù)責(zé)人 何彥青 yqhe 本小節(jié)介紹短語抽取模塊 從詞對齊的語料庫中自動學(xué)習(xí)漢語短語到英語短語的翻譯 2 3 1 模塊定義模塊定義 1 輸入文件 詞語對齊的語料庫 2 輸出文件 短語翻譯概率表 3 功能說明 從詞語對齊的語料庫中抽取雙語短語 并計算翻譯概率 p c e lex c e p e c lex e c 2 3 2 實現(xiàn)原理實現(xiàn)原理 許多基于短語的統(tǒng)計機器翻譯系統(tǒng)的短語抽取方法都很相似 根據(jù)這些方法 本模塊實 現(xiàn)了從詞對齊中自動抽取雙語短語的算法 基本思想就是首先根據(jù)詞對齊生成最大似然詞匯 化詞典 然后進(jìn)行短語抽取 最后對每一個短語對計算 4 個翻譯概率 2 3 2 1 生成最大似然詞匯化翻譯表生成最大似然詞匯化翻譯表 對于已經(jīng)進(jìn)行了詞對齊的語料 直接估計最大似然詞匯化翻譯表 用于短語對的詞匯化 概率計算 如果直接用 GIZA 產(chǎn)生的翻譯表計算 由于有的詞條在 GIZA 詞典中沒有出 現(xiàn) 導(dǎo)致會有一些短語對的詞匯化概率為 0 而且 GIZA 詞典中沒有 w c NULL 和 w e NULL 這兩個概率值 直接估計的方法就是直接抽取對齊的詞對 如果某個詞沒有與之 對齊的翻譯詞 就認(rèn)為它與 NULL 對齊 然后計算同現(xiàn)次數(shù) 按照下面公式分別計算出 w e f 和 w f e 從而直接生成詞匯化翻譯表 f count e f w f e counte f 公式 3 e count e f w e f count e f 公式 4 2 3 2 2 短語抽取短語抽取 從詞語對齊的語料庫中抽取雙語短語 要求短語對必須與詞對齊相容 定義如下 e fBP iijj eeefAff AND jiji ffe fAee 公式 5 其中 A 表示詞語對齊的矩陣 抽取方法就是提取對齊矩陣中的所有以對齊點為頂點的矩形 條件是與矩形所在行范 圍內(nèi)的源詞對齊的目標(biāo)詞也都在這個矩形的列范圍內(nèi) 反之亦然 例如 23 中國 化學(xué) 工業(yè) 保持 穩(wěn)定 增長 China s chemical industry maintains steady growth 圖 7 短語抽取示例 對于上例 抽取出的短語結(jié)果為 表 17 短語抽取結(jié)果 這個結(jié)果中每一行格式如下 中文短語 英文短語 詞語對齊 中 英 中國 China s 0 0 0 1 中國 化工 China s chemical 0 0 0 1 1 2 中國 化工 工業(yè) China s chemical industry 0 0 0 1 1 2 2 3 中國 化工 工業(yè) 保持 China s chemical industry maintains 0 0 0 1 1 2 2 3 3 4 中國 化工 工業(yè) 保持 穩(wěn)定 China s chemical industry maintains steady 0 0 0 1 1 2 2 3 3 4 4 5 中國 化工 工業(yè) 保持 穩(wěn)定 增長 China s chemical industry maintains steady growth 0 0 0 1 1 2 2 3 3 4 4 5 5 6 化工 chemical 0 0 化工 工業(yè) chemical industry 0 0 1 1 化工 工業(yè) 保持 chemical industry maintains 0 0 1 1 2 2 化工 工業(yè) 保持 穩(wěn)定 chemical industry maintains steady 0 0 1 1 2 2 3 3 化工 工業(yè) 保持 穩(wěn)定 增長 chemical industry maintains steady growth 0 0 1 1 2 2 3 3 4 4 工業(yè) industry 0 0 工業(yè) 保持 industry maintains 0 0 1 1 工業(yè) 保持 穩(wěn)定 industry maintains steady 0 0 1 1 2 2 工業(yè) 保持 穩(wěn)定 增長 industry maintains steady growth 0 0 1 1 2 2 3 3 保持 maintains 0 0 保持 穩(wěn)定 maintains steady 0 0 1 1 保持 穩(wěn)定 增長 maintains steady growth 0 0 1 1 2 2 穩(wěn)定 steady 0 0 穩(wěn)定 增長 steady growth 0 0 1 1 增長 growth 0 0 24 2 3 2 3 計算概率計算概率 短語抽取完后 再計算四個翻譯概率 p c e lex c e p e c lex e c 計 算方法就是對所有生成的短語對分別計算英文短語 中文短語以及二者的同現(xiàn)次數(shù) 然后求 商 得 到 p c e 和 p e c 然 后 利 用2 3 2 1中 生 成 的 詞 典 按 照 11 1 1 J JI ji j iaj lex ceap ce ij ia 公式 2 計算 lex c e 和 lex e c 例如 中國 化學(xué) China s chemical 圖 8 短語詞匯化翻譯概率的計算 2 3 3 使用說明使用說明 按照 2 3 2 介紹的原理程序也相應(yīng)分為三部分 生成詞典 抽取短語和計算概率 該模 塊基于 vc 6 0 以及 linux 平臺編寫 分別放在 dict pharaoh 和 com prob 三個文件 夾下 2 3 3 1 程序程序 1 生成詞典 生成詞典 1 主程序為 dictionary cpp 如要修改文件名或路徑 請在 definev h 中修改 2 請先在當(dāng)前目錄下建立一個 data 文件夾 將絲路說明中要求的 xml 格式的對齊文 件放入 data 文件夾中 格式同表 6 3 輸出文件也放在 data 文件夾中 分別為 en ch txt 英中單詞概率文件 表示 w c e 格式為 personnel 隊伍 0 0170758 constantly 經(jīng)常 0 0833333 sound 聲調(diào) 0 000423729 ch en txt 為中英單詞概率文件 表示 w e c 格式為 Jakes Jakes 0 5 能 indulge 0 000129224 干警 police 0 166667 芯片 the 0 0483871 一致 NULL 0 185687 lex 中國 化工 China s chemical 1 2 w 中國 China w 中國 s w 化工 chemical 25 2 3 3 2 程序程序 2 短語抽取 在 pharaoh 文件夾中 短語抽取 在 pharaoh 文件夾中 1 主程序為 extract phrase cpp 如要修改文件名或路徑 請在 definev h 中修 改 2 請先在當(dāng)前目錄下建立一個 data 文件夾 將絲路要求的 xml 格式的對齊文件放 入 data 文件夾中 格式同表 6 3 輸出文件在 data 文件夾下 Phrase Extraction txt 不帶概率的短語抽取結(jié)果 格式如下 BritneySpears Britney Spears 0 0 0 1 BritneySpears Britney Spears 0 0 0 1 1 2 BritneySpears BackstreetBoys Britney Spears Backstreet Boys 0 0 0 1 1 2 2 3 2 4 BritneySpears BackstreetBoys Britney Spears Backstreet Boys 0 0 0 1 1 2 2 3 2 4 3 5 注 這個輸出文件 Phrase Extraction txt 中有重復(fù)的短語 2 3 3 3 程序程序 3 計算概率 在 com prob 文件夾中 計算概率 在 com prob 文件夾中 1 主程序為 com prob cpp 如要修改文件名或路徑 請在 defive h 中修改 2 請先在當(dāng)前目錄下建立一個data文件夾 將以下運行程序所需的文件放入data 文件夾中 Phrase Extraction txt 不帶概率的短語抽取結(jié)果 也就是程序 2 的結(jié)果 en ch txt 為英中單詞概率文件 程序 1 的輸出結(jié)果 ch en txt 為中英單詞概率文件 程序 1 的輸出結(jié)果 3 輸出文件在 data 文件夾下 為 Phrase Probability txt 是含有概率的短語 抽取結(jié)果 格式如下 1 0 0683137 1 0 546206 BritneySpears Britney Spears 1 0 00406288 1 0 01701 BackstreetBoys Backstreet Boys 1 0 000825138 1 0 03945 BritneySpears BackstreetBoys Britney Spears Backstreet Boys 1 4 90742e 005 1 0 00122855 BackstreetBoys Backstreet Boys 1 0 0120787 1 0 0722254 注 輸出文件 Phrase Probability txt 剔除了重復(fù)的短語 2 3 3 4 參數(shù)說明參數(shù)說明 程序參數(shù)可以在 defive h 中修改 抽取短語最大長度 只對中文短語限制了長度 EXTRACTLEN 8 輸入文件每行的最大長度 SENTENCELEN 3000 輸入文件每句中的最大詞數(shù) PHRASEN 100 每個詞中的最大字符數(shù) PHRASEL 20 26 27 3 解碼模塊設(shè)計與使用解碼模塊設(shè)計與使用 3 1 輸入預(yù)處理輸入預(yù)處理 在進(jìn)行解碼前 需要對測試文件進(jìn)行預(yù)處理 這一部分同 2 1 節(jié)的訓(xùn)練語料預(yù)處理是類 似的 需要進(jìn)行漢語的分詞 以及漢語全角字符的替換 3 2 語言模型接口使用說明語言模型接口使用說明 負(fù)責(zé)人 侯宏旭 hxhou 我們在 SRILM 1 4 5 版本的基礎(chǔ)上 利用原有函數(shù)庫 編寫了語言模型的調(diào)用接口 接 口包含語言模型函數(shù)庫 lmsridll dll 和壓縮函數(shù)庫 zlib1 dll 編程接口包含 lmsridll lib 接口函 數(shù)庫和 lmsridll h 頭文件 接口函數(shù)如下 void sriLoadLM const char fn int arpa 0 int order 3 int unk 0 int tolow 0 載入語言模型 fn 文件名 支持的文件類型有兩種 普通文本文件和 gzip 壓縮文件 擴展名為 gz 的 文件 arpa ARPA 格式和 BIN 格式 0 為 BIN 格式 非 0 為 ARPA 格式 order 讀入元數(shù) 缺省為 3 unk 保留 缺省不保留 tolow 全部轉(zhuǎn)化為小寫 缺省不轉(zhuǎn)化 返回語言模型的指針 int sriSetOrder void plm int o 設(shè)定最大元數(shù) plm 語言模型的指針 o 新的元數(shù) 小于等于 0 時無效 不變 大于語言模型數(shù)據(jù)的元數(shù)時按語言模型數(shù)據(jù) 的元數(shù)計算 返回原來的元數(shù) void sriUnloadLM void plm 卸載語言模型 plm 語言模型的指針 double sriPerplexity void plm const char sentence 計算句子困惑度 plm 語言模型的指針 sentence 句子 返回句子的困惑度 perplexity a1 a2 a3 an log10 P a1 P a2 a1 P a3 a1a2 P an a1 an 1 28 double sriWordProb void plm const char word const char context 計算 n gram plm 語言模型指針 返回值 log10 P word context 29 3 3 駱駝 駱駝 CAMEL 解碼器 解碼器 負(fù)責(zé)人 何中軍 zjhe 駱駝CAMEL 是一個統(tǒng)計機器翻譯解碼器 是 絲路 的一個組成部分 采用Log linear 直接翻譯模型 Och string phrase ChineseWord start end Search translation options for phrase from Bilingual Phrase table 算法 2 Select Translation Options 模塊模塊 2 計算未來概率 計算未來概率 Compute Future Cost 在搜索過程中 我們以 Hypothesis 來存儲英語短語翻譯及概率等信息 并將已翻譯相同 個數(shù)漢語詞語的 Hypothesis 存儲到同一個棧中 為了減小搜索空間 采用寬度優(yōu)先的柱式搜 索 Beam Search 這樣需要對同一個棧中的 Hypothesis 進(jìn)行剪枝 盡管同一個棧中存放的 Hypothesis 覆蓋的漢語詞個數(shù)相同 但是其覆蓋的位置可能不同 在剪枝時 為了進(jìn)行比較 不僅要考慮當(dāng)前概率 已翻譯詞的概率 還要考慮未來概率 翻譯目前為止還未翻譯的詞 語需要的最大概率 未來概率是指如果要完成整個句子的翻譯 剩余部分達(dá)到的最大概率 即最小代價 它跟當(dāng)前還未翻譯的詞語相關(guān) 根據(jù)短語翻譯概率 短語長度及語言模型進(jìn)行估算 在 Translation Options 中 每一個漢語短語 end start f 都對應(yīng)一個或多個英語翻譯 利用下式求得 end start f 的最大翻譯概率 maxlog end startii TP fp e f 公式 7 其中 i p e f 指短語的 4 個翻譯概率 英語短語長度 以及英語短語語言模型概率 然后 利用動態(tài)規(guī)劃算法 可以很容易的求得任意連續(xù)串的未來概率 請參考算法 1 算法 3 32 for each ChinesePhrase in Translation Option maxlog end startii TP fp e f FutureCost start end TP for len 1 to ChineseWord size for i 0 to ChineseWord size len for j i to i len double p FutureCost i j FutureCost j 1 i len if p FutureCost i i len FutureCost i i len p 算法 3 Compute Future Cost 例如 對于漢語句子 中國 經(jīng)濟 發(fā)展 十分 迅速 根據(jù) Translation Options 和 maxlog end startii TP fp e f 公式 7 計算得到的漢語短語最大 翻譯概率如圖 10 中國 0 經(jīng)濟 1 發(fā)展 2 十分 3 迅速 4 1 9118 1 8484 2 2069 2 1182 2 2024 4 6019 4 7869 2 5177 圖 10 漢語短語最大概率 則根據(jù)算法 3 FutureCost 0 1 FutureCost 0 0 FutureCost 1 1 3 7602 公式 8 同樣的也可以計算其他任意連續(xù)位置的 FutureCost 在解碼時 如果未翻譯的漢語詞是不連續(xù)的 那么我們將各個連續(xù)位置的 FutureCost 相加 作為這個 Hypothesis 的 FutureCost 例如 如果一個假設(shè) h 翻譯了單詞 發(fā)展 則 未翻譯的片斷為 0 1 3 4 那么 FutureCost h FutureCost 0 1 FutureCost 3 4 公式 9 模塊模塊 3 柱式搜索 柱式搜索 Beam Search 搜索是解碼器的核心 Translation Options 的選擇和 Future Cost 的計算都是為搜索作準(zhǔn) 備的 CAMEL 采用柱式搜索 Beam Search 策略 每次只保留最好的 N 個決策 實際上 它是一種寬度優(yōu)先搜索算法 對于一個漢語句子 已分詞 12 n c cc 解碼器每次都根據(jù) Translation Options 選擇 句子中未翻譯的一個片斷 即短語 ij cc 進(jìn)行翻譯 根據(jù)公式 4 計算相應(yīng)概率 產(chǎn)生英 語短語翻譯 并將這些信息存儲于 Hypothesis 中 根據(jù)已經(jīng)翻譯的單詞個數(shù) m 將新產(chǎn)生的 33 Hypothesis 存儲到相應(yīng)的棧 stack m 中 當(dāng)一個句子翻譯完畢時 關(guān)于這個句子的完整翻譯 信息可以從最后一個棧 stack n 中向前回溯得到 請參考算法 4 initialize HypothesisStack 0 nf create initial Hypothesis hp init and push to HypothesisStack 0 for i 0 to nf 1 for each hypothesis in HypothesisStack i for each new hp that can be derived from hp covered number number of foreign words coverd so far push new hp to HypothesisStack covered number prune HypothesisStack covered number 算法 4 Beam Search 下面對 Hypothesis 數(shù)據(jù)結(jié)構(gòu)和剪枝策略進(jìn)行詳細(xì)說明 1 Hypothesis 數(shù)據(jù)結(jié)構(gòu) 在搜索過程中 各種信息都存儲在 Hypothesis 中 翻譯一個句子的過程 也 就是擴展 Hypothesis 的過程 Hypothesis 中需要包含以下信息 指向父親結(jié)點的指針 便于回溯產(chǎn)生路徑 目前為止翻譯的漢語詞 一個 bool 型的數(shù)組 已翻譯的詞標(biāo)記為 1 未翻譯的 詞標(biāo)記為 0 上一次翻譯的漢語短語最后一個漢語詞的位置 計算扭曲概率 目前為止產(chǎn)生的最后兩個英語詞 計算 3 gram 語言模型 本次擴展的漢語短語對應(yīng)的英語翻譯 特征函數(shù) 包括翻譯概率 英語短語長度 語言模型概率 扭曲距離 目前為止的概率 P 未來概率 FC 估計概率 EC EC P FC 被合并掉的其他邊的信息 Additional Arc 父親節(jié)點 英語譯文 概率 2 剪枝策略 1 Recombining Hypothesis 第一種方法是 Hypothesis 的合并 這是一種沒有風(fēng)險 risk free 的剪枝策略 也即合并不會損失任何信息 如果兩個假設(shè) Hp1 和 Hp2 滿足以下三個條件 我們 就可以將它們合并 覆蓋的漢語詞位置相同 最后產(chǎn)生的兩個英語詞相同 如果是 3 gram 語言模型 前一次翻譯的漢語短語最后一個詞的位置相同 如果 Hp1 的估計概率 EC1 大于 Hp2 的估計概率 EC2 那么我們就保留 Hp1 繼續(xù)擴展 而將 Hp2 的相關(guān)信息 父親節(jié)點 英語譯文 概率 保存到 Hp1 中的 Additional Arc 中 反之則將 Hp1 合并到 Hp2 中 這樣概率低的 Hypothesis 不會再 繼續(xù)擴展 但是在回溯的時候仍然可以根據(jù)保留的信息將其找回 3 剪枝策略 2 Histogram Pruning 第二種方法是柱狀圖剪枝 這是一種有風(fēng)險的剪枝策略 被剪掉的邊將從棧中 34 刪除 以后也不會再擴展 無法回溯找到 解碼器將每個棧的大小限定為一個特定值 N 搜索時 如果棧中的元素個數(shù)小 于 N 則可以繼續(xù)壓入元素 如果棧中的元素個數(shù)等于 N 那么就將棧中概率最 小 即估計概率 EC 最小 的元素刪除 然后再壓入元素 模塊模塊 4 譯文的產(chǎn)生 譯文的產(chǎn)生 Generate N best List 搜索完畢 可以通過回溯產(chǎn)生最終譯文 一般的 我們只產(chǎn)生一個最好的譯文 1 best 即從最后一個棧中找到概率最大的 Hypothesis 根據(jù)其指向父親節(jié)點的指針向前回溯 有些 時候 比如訓(xùn)練 Log linear 模型的參數(shù) Och 2003 或者用 N best 做 Rerank 等 可能會需 要解碼器輸出多個譯文 N bset 我們利用 A 算法來產(chǎn)生 N best 下面分別對這兩種方法 進(jìn)行介紹 1 Generate 1 best 產(chǎn)生 1 best 的方法非常簡單 只需要從最后一個棧中找到概率最大的 Hypothesis 向前回 溯即可 請參考算法 5 find the Hypothesis with the highest probability in HypothesisStack nf english translation hyp best english father hyp hyp best father while father hyp hyp init english translation father hyp english english translation father hyp father hyp father output english translation 算法 5 Generate 1 best 2 Generate N best 有 很 多 種 方 法 可 以 產(chǎn) 生N best 如 利 用 有 限 狀 態(tài) 自 動 機 工 具Carmel http www isi edu licensed sw carmel CAMEL 采用 A 算法 Och et al 2001 來產(chǎn)生 N best 35 3 3 3 使用說明使用說明 本節(jié)介紹 CAMEL 的使用方法 3 3 3 1 安裝安裝 硬件要求 PC 機 P4 2 0GHz 以上 CPU 512M 以上內(nèi)存 硬盤 40G 以上 軟件要求 CAMEL V1 0 使用 C 開發(fā) 可以運行在 GNU Linux 平臺和 Win32 平臺 以下 兩種編譯器都可以進(jìn)行編譯 1 GNU C 編譯器 Version3 3 或更高 2 Microsoft C 7 1 Linux 下的安裝 下載 CAMEL v1 0 Linux tar gz 將其拷貝到任一目錄 使用下面的命令解壓縮 tar zxvf CAMEL v1 0 Linux tar gz 進(jìn)入 CAMEL 目錄 鍵入 make 命令進(jìn)行編譯 make 如果編譯過程中語言模型鏈接出錯 可能是由于 Linux 版本不同所致 請重新 編譯語言模型庫 覆蓋程序包中 srilm lib 下的 a 文件 并重新編譯 方法如下 a 將程序包中的 srilm tar gz 解壓縮 b 在 srilm 目錄下 鍵入 make 進(jìn)行編譯 c 編譯完成 在 srilm 目錄下會生成 lib 目錄 將其下面的 a 文件拷貝到 Camel 軟件包中的 srilm lib 目錄下 覆蓋里面的 a 文件 d 重新編譯 Camel 3 3 3 2 運行解碼器運行解碼器 鍵入以下命令 運行解碼器 CAMEL conf configurefile test file testfile result file resultfile 解碼器讀入配置文件和測試文件 輸出結(jié)果文件 下面詳細(xì)介紹配置文件及命令行參 數(shù) 1 配置文件 配置文件對解碼器的各項參數(shù)進(jìn)行設(shè)置 格式如表 18 36 ttable limit 10 stack 100 nbest list 200 distortion 0 ttable file bp 4k 12 11 txt lm file 30k3gram gz lm ngram 3 para p c e 0 03 lex c e 0 03 p e c 0 15 lex e c 0 16 len 0 48 lm 0 13 dis 0 end print info 0 print nbest 0 表 18 解碼器配置文件格式 2 文件參數(shù) ttable file 指定雙語短語文件的位置 lm file 指定語言模型的位置 lm ngram 指定語言模型的元數(shù) 默認(rèn)是 3 gram 3 特征函數(shù)的權(quán)重 CAMEL 采用 Log linear 直接翻譯模型 共有 7 個特征 這些特征的權(quán)重在配置文件中 設(shè)置 para 和 end 中間的部分 其中前 4 個是短語翻譯概率的權(quán)重 len 是英語句子長度的權(quán)重 lm 是語言模型的權(quán)重 dis 是短語扭曲模型的權(quán)重 4 剪枝參數(shù) CAMEL 采用 2 種類型的剪枝 對短語表進(jìn)行剪枝以限制讀入短語的數(shù)量 搜索過程中 對搜索棧進(jìn)行剪枝 ttable limit 對雙語短語表進(jìn)行剪枝 由于雙語短語表是從平行語料庫中自動抽取得到的 同一個漢語短語可能對應(yīng)多個 甚至上百個不同的英語短語翻譯 一種方法是 對同一個漢語短語 只取 最好 的 N 個英語短語 在我們的系統(tǒng)中 默認(rèn)是 10 所謂 好 的翻譯 我們用短語翻譯概率來衡量 概率越大越 好 log ii Pp e f 公式 10 37 其中 i p e f 表示短語翻譯的 4 個概率 i 表示對應(yīng)的權(quán)重 這個參數(shù)也可以在命令行中進(jìn)行設(shè)置 stack 對搜索棧進(jìn)行剪枝 解碼器采用 Beam Search 方法進(jìn)行搜索 數(shù)據(jù)存放于棧中 在搜索過程中 對棧的大小 進(jìn)行限制 以減少搜索空間 更詳細(xì)的說明請參考第 2 章 Beam Search 在我們的系統(tǒng)中 棧的大小默認(rèn)是 100 這個參數(shù)也可以在命令行中進(jìn)行設(shè)置 5 distortion 對短語扭曲距離進(jìn)行限制 扭曲模型的計算公式如下 di i Pd 公式 11 其中 d abs last word position of previously translated phrase 1 first word position of newly translated phrase 對短語扭曲距離進(jìn)行限制 也可以極大的減少搜索空間 默認(rèn)值是 5 即 d 5 如果 將 distortion 設(shè)為 0 則不進(jìn)行調(diào)序 即單調(diào)搜索 這個參數(shù)也可以在命令行中進(jìn)行設(shè)置 6 nbest list 對于一個源語言句子 解碼器可以產(chǎn)生 1 個或多個目標(biāo)語言句子 默認(rèn)的 Nbest 大小是 200 這個參數(shù)也可以在命令行中進(jìn)行設(shè)置 Parameters ttable limit number of phrase translations for each foreign phrase default 10 Parameters stack maximum size of the beam default 100 Parameters distortion maximum distance between two foreign phrases default 5 0 for monotone search Parameters nbest list number of candidate translations for each input sentence default 100 38 7 print info 用于輸出對一個句子進(jìn)行解碼的詳細(xì)信息 包括可適用的英語短語 未來概率 Future Cost 搜索過程 以及回溯產(chǎn)生的 Nbest 路徑 如果 print info 設(shè)為 1 則解碼器會產(chǎn)生 一個 search info xml 文件 包含 4 部分內(nèi)容 格式如下 第一部分 顯示 TranslationOption 找到所有能夠適用于該句子的英語短語 中國 經(jīng)濟 發(fā)展 十分 迅速 0 282683 0 242107 0 995656 0 391329 1 0 331812 0 69002 1 76154 1 87886 2 0 344841 0 916413 0 904456 2 43623 3 0 241162 1 04799 1 33977 2 98078 3 表 19 TranslationOption 其中 后面 前四個數(shù)值是短語翻譯概率取 log 以后的數(shù)值 第 5 個數(shù)值是英語短語的長度 39 第二部分 顯示 FutureCost 根據(jù) Translation Options 來估算翻譯所有連續(xù)漢語片段的 最大概率 即最小代價 4 85626 6 62409 7 11725 17 5915 27 7396 7 43527 3 31509 13 7893 23 9374 5 58266 16 0569 26 205 10 4742 20 6223 10 1481 表 20 FutureCost 第三部分 顯示搜索棧中的信息 在搜索過程中 以Hypothesis來保存信息 將Hypothesis 按照已翻譯的漢語詞個數(shù)保存到相應(yīng)的棧中 1 1 1 0 0 development economy development 2 2 0 424533 0 428234 0 954138 0 399975 1 5 94549 0 total probability 15 6421 sigma function 7 15237 1 0 economy development 0 0 786202 3 16407 1 50189 2 5 68787 0 total probability 16 3624 sigma function 9 14003 表 21 Stack information 40 表示第 3 個棧 也即已經(jīng)翻譯了 3 個漢語詞 棧中有 4 個元素 表示第 3 個棧中第 0 個 Hypothesis 與中間是 Hypothesis 中的信息 Father 2 1 表示其父親結(jié)點是第 2 個棧中的第 1 個 Hypothesis 注意 棧中的 Hypothesis 從 0 開始編號 與顯示了已經(jīng)翻譯的漢語詞的信息 與表示本假設(shè)生成的英語翻譯 與表示到目前為止 最后產(chǎn)生的 2 個英語單詞 如 果是 3 元語言模型的話 2 2 表示本假設(shè)翻譯的漢 語短語位置是 2 2 上一次翻譯的漢語短語最后一個位置是 1 用于計算扭曲模型 與顯示概率信息 分 別是短語翻譯概率 前 4 個 短語長度 語言模型概率 扭曲距離 total probability 表示 到目前為止走過的路徑的概率和 sigma function 僅指本假設(shè)概率的加權(quán)和 即 log ii Pp e f 公式 12 FutureCost 可以查表得到 EstimateProb total probability FutureCost 與表示搜索過程中被合并掉的邊 num 表示邊的個數(shù) 每一個都是一條被合并掉的邊 記錄了其父親結(jié)點 英語翻譯 以及概率信息 用于生成 Nbest list 第四部分 顯示 Nbest list 即搜索產(chǎn)生的 N 個候選翻譯 China s economic development extremely rapidly 0 652326 2 1119 2 10987 4 23355 6 27 0231 0 total probability 30 1308 sigma function 30 1308 China s economic development extremely rapid 1 75094 2 67437 3 28852 5 18906 6 27 0494 0 total probability 33 9523 sigma function 33 9523 表 22 Nbest list 這個參數(shù)也可以在命令行中進(jìn)行設(shè)置 Parameters print info print decoding information or not default 0 41 8 print nbest 如果只想查看 Nbest 信息 那么可以將本參數(shù)設(shè)為 1 輸出格式如下 中國 經(jīng)濟 發(fā)展 十分 迅速 China s economic development extremely rapidly 0 652326 2 1119 2 10987 4 23355 6 27 0231 0 China s economic development extremely rapid 1 75094 2 67437 3 28852 5 18906 6 27 0494 0 表 23 單獨的 Nbest List 其中 表示第 1 個漢語句子 有 2 個英