《機器翻譯理論和技術.ppt》由會員分享，可在線閱讀，更多相關《機器翻譯理論和技術.ppt（126頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、機器翻譯理論和技術,,主要內容,機器翻譯概述 機器翻譯的歷史 機器翻譯與自然語言處理 機器翻譯所涉及的學科 機器翻譯基本策略和實現(xiàn)方法 機器翻譯的難點 機器翻譯的現(xiàn)狀,傳統(tǒng)的（基于規(guī)則）機器翻譯方法（理性方法） 詞法分析 詞性標注 分詞（漢語、日語） 句法分析 基于CFG（上下文無關文法）的句法表示及其分析技術 基于擴充的CFG（復雜特征集、合一運算）的句法表示及其分析技術 語義分析 詞義及句義表示 基于格語法的句義分析 轉換、生成技術,主要內容（續(xù)1）,基于語料庫的機器翻譯方法（經(jīng)驗方法） 基于統(tǒng)計的機器翻譯方法 語言模型（ N元文法） HMM模型與詞性標注 PCFG文法與句法分析 統(tǒng)計機器

2、翻譯模型（SMT） 基于實例的機器翻譯方法 基于混合策略的機器翻譯方法,主要內容（續(xù)2）,所需的前導知識,形式語言與自動機 編譯技術 概率與統(tǒng)計,參考書籍,趙鐵軍等，機器翻譯原理，哈爾濱工業(yè)大學出版社，2000 劉群等譯，自然語言理解（第二版），電子工業(yè)出版社，2005 苑春法等譯，統(tǒng)計自然語言處理基礎，電子工業(yè)出版社，2005 馮志偉等譯，自然語言處理綜論，電子工業(yè)出版社，2005 范明等譯，統(tǒng)計學習基礎--數(shù)據(jù)挖掘、推理與預測，電子工業(yè)出版社，2004 王小捷等，自然語言處理技術基礎，北京郵電大學出版社,2002 劉穎，計算語言學，清華大學出版社，2002 姚天順，自然語言理解一種讓機器懂

3、得人類語言的研究（第2版），清華大學出版社，2002 黃昌寧等，語料庫語言學，商務印書館，2002 馮志偉，計算語言學基礎，商務印書館，2001 余士文，計算語言學概論，商務印書館，2003,Bonnie J. Dorr, et al, Survey of Current Paradigms in Machine Translation，Technical Report LAMP-TR-027, Language and Media Processing Lab, University of Maryland. Hutchins WJ, Machine Translation: Past, P

4、resent, Future. Chichester: Ellis Horwood, 1986 Arturo Trujillo, Translation Engines: Techniques for Machine Translation, Springer-Verlag London Limited 1999 Peter F. Brown, et al., A Statistical Approach to MT, Computational Linguistics, 1990,16(2) P.F. Brown, et al., The Mathematics of Statistical

5、 Machine Translation: Parameter Estimation, Computational Linguistics, 1993, 19(2),Makoto Nagao, A Framework of a Mechanical Translation between Japanese and English by Analog Principle, In A. Elithorn and R. Banerji(Eds.), Artificial and Human Intelligence. NATO Publications, 1984 James Allen, Natu

6、ral Language Understanding, The Benjamin/Cummings Publishing Company, Inc. 1987 Christopher D. Manning & Hinrich Schutze, Foundations of Statistical Natural Langugae Processing, Massachusetts Institute of Technology, 1999 Daniel Jurafsky & James H. Martin, Speech and Language Processing, Prentice-Ha

7、ll, 2000 Trevor Hastie, et al., The Elements of Statistical Learning--Data Mining, Inference, and Prediction, Springer-Verlag, New York, 2001,課程考核,Projects 提交要求（每個project） 報告（說明基本做法） 源程序及可運行的程序,機器翻譯概述,機器翻譯（Machine Translation，簡稱MT）是指利用計算機實現(xiàn)自然語言（英語、漢語等）之間的自動翻譯。 文本機器翻譯 語音機器翻譯 機器輔助翻譯（Machine Aided Tran

8、slation或Computer Aided Translation，簡稱MAT或CAT） 翻譯記憶體（Translation Memory，簡稱TM） 雙語對照的文本編輯 ...,機器翻譯歷史,1947，Warren Weavers memo 1954，第一個公開展示的俄英MT原型系統(tǒng) 1966，美國科學院的ALPAC報告宣告機器翻譯走入低谷 1970s，Systran（1970），Meteo（1976）， Early 1980s，復蘇，Eurotra，Mu Late 1980searly 1990s，商品化系統(tǒng)投入市場，語音翻譯，統(tǒng)計機器翻譯 Late 1990s，Internet，MAT

9、，EBMT,I have a text in front of me which is written in Russian but I am going to pretend that it is really written in English and that it has been coded in some strange symbols. All I need do is strip off the code in order to retrieve the information contained in the text,,機器翻譯與自然語言處理,自然語言處理（NLP）是指用

10、計算機對語言信息進行處理的方法和技術。 與NLP相近的兩個研究領域： 自然語言理解(NLU)：強調對語言含義和意圖的深層次解釋 計算語言學(CL)：強調可計算的語言理論,NLP技術的應用,機器翻譯 自動摘要 文本分類 信息檢索 信息抽取 自動問答 情感分析 ......,自動摘要（Text Summarization）,利用計算機自動地從原始文檔中提取全面準確地反映該文檔中心內容的簡單連貫的短文。 壓縮比,文本分類（Text Classification）,利用計算機將一篇文章歸于預先給定的某一類或某幾類的過程。 文本表示 相似度計算 可用于信息過濾（Information Filtering

11、）,信息檢索（Information Retrieval，IR）,主題相關的文本獲取。 google、百度、...（基于關鍵詞的） 倒排文檔,信息抽?。↖nformation Extraction，IE）,主題相關的信息獲取 信息抽取是指從非結構化或半結構化的自然語言文本中提取出與某個主題相關的結構化信息。 IE對數(shù)據(jù)挖掘的支持,新華社北京月日電（記者李術峰）: 中國農(nóng)工民主黨第十二屆中央常務委員會第一次會議今天在北京召開。 會議研究通過了貫徹落實“兩會”精神的有關決定，審議通過了中國農(nóng)工民主黨中央年工作要點（草案），并任命了中央副秘書長。 農(nóng)工民主黨中央主席蔣正華主持了會議，他說，農(nóng)工民主黨

12、有多名黨員作為代表和委員參加了今年的“兩會”，各位黨員要認真履行代表和委員的職責，開好會，在年的工作中認真貫徹“兩會”精神，加強農(nóng)工民主黨的自身建設，推動事業(yè)進一步發(fā)展，為建設有中國特色社會主義事業(yè)作出新的貢獻。 會前，農(nóng)工民主黨中央邀請參加“兩會”的來自全國各省、自治區(qū)、直轄市的農(nóng)工民主黨黨員進行了聯(lián)誼活動。,信息抽取實例:會議報道(人民日報1998-03-09),信息抽取的結果,自動問答（Question Answering，QA）,針對用戶提出的問題，給出具體的答案。 問句理解和答案生成。,情感分析（Sentiment Analysis或 Opinion Analysis ）,分析文章對

13、某個對象的態(tài)度是正面還是負面。 應用于：市場決策、公共關系、...,自然語言處理的主要任務,語言分析 詞法分析：形態(tài)還原、詞性標注、命名實體識別、分詞（漢語）等 句法分析：完全句法分析、組塊分析、依存分析 語義分析：詞義、句義（依存、格關系、...）、篇章（上下文分）（指代、實體關系） 語言生成 多語言處理：對齊、轉換 不同的應用對上述任務有不同的要求。 MT是NLP技術的典型應用，它幾乎涵蓋了NLP各個任務。,自然語言處理所涉及的學科,計算語言學：各種語法、語義理論 計算機科學（包括人工智能） 數(shù)學：邏輯、概率與統(tǒng)計、信息論，等 哲學 心理學,直譯（Direct）：從原文句子的表層（詞、詞組

14、或短語）出發(fā)，直接轉換成譯文（必要的詞序調整）。 轉換（Transfer）：對源語言進行分析，得到一個基于源語言的中間表示；然后，把這個中間表示轉換成基于目標語言的中間表示；從基于目標語言的中間表示生成目標語言。 中間語（Interlingua）：對源語言進行分析，得到一個獨立于源語言和目標語言的、基于概念的中間表示；從這個中間表示生成目標語言。,機器翻譯的基本策略,,,,中間語言,源語言,目標語言,,,,,,分析,生成,詞匯轉換,句法轉換,語義轉換,(詞法、句法、語義),(詞法、句法、語義),機器翻譯的實現(xiàn)方法,基于語言規(guī)則的理性方法（Rationalist approach） 基于以規(guī)則形

15、式表達的語言知識（詞、句法、語義以及轉換）進行推理。（Rule-based MT） 又稱傳統(tǒng)的翻譯方法，強調人對語言知識的理性整理。 Chomsky：先天語言能力，主宰19601985 基于語料庫的經(jīng)驗方法（Empiricist approach） 以大規(guī)模語料庫（單語和雙語）為語言知識基礎。包括： 基于統(tǒng)計的方法（SMT） 利用統(tǒng)計學習方法自動獲取和運用隱含在語料庫中的知識 翻譯知識的獲取在翻譯之前完成，體現(xiàn)為一系列統(tǒng)計數(shù)據(jù)（參數(shù)） 基于實例的方法（EBMT） 基于類比原理，通過相似度計算，在語料庫中找出最相似的句子 翻譯知識的獲取在翻譯之前沒有全部完成,翻譯過程中還需要語料庫,混合方法 理

16、性方法的優(yōu)、缺點 相應的語言學理論基礎好 描述精確 效率高 知識獲取困難（高級勞動） 魯棒性（適應性）差：不完備的規(guī)則系統(tǒng)將導致推理的失敗 知識擴充困難，很難保證規(guī)則之間的一致性 經(jīng)驗方法的優(yōu)、缺點 知識獲取容易（低級勞動） 魯棒性好：概率大的作為結果 擴充容易、一致性容易維護 相應的語言學理論基礎差 缺乏對語言學知識的深入利用，過于機械 效率低 利用各家之長，相互融合,機器翻譯的難點,歧義處理：有限的詞匯和規(guī)則表達復雜的、無限的語言 語言知識的表示、獲取和運用 成語和慣用型的處理 對語言的靈活性和動態(tài)性的處理 靈活性：同一個意圖的不同表達，甚至包含錯誤的語法等 動態(tài)性：語言在不斷的變化，如：

17、新詞等 上下文和世界知識（語言無關）的利用和處理,漢語處理的難點,缺乏計算語言學的句法/語義理論，大都借用基于西方語言的句法/語義理論 詞法分析 分詞 詞性標注難 句法分析 主動詞識別難 詞法分類與句法結構對應差 語義分析 句法結構與句義對應差 時體態(tài)確定難 （漢語無形態(tài)變化） 資源（語料庫）缺乏,機器翻譯的現(xiàn)狀,目前，機器翻譯主要在一些簡單的翻譯任務中起到了一定的效果： 對翻譯質量要求不高的領域，如：網(wǎng)頁瀏覽等 子語言 輔助翻譯（后編輯） 任意文本的高質量的全自動翻譯目前還很難實現(xiàn)。,傳統(tǒng)的（基于規(guī)則）機器翻譯方法,又稱理性方法 強調對語言知識的理性整理 受計算語言學理論指導 注重語言分析，

18、翻譯過程體現(xiàn)為“分析（轉換）生成” 基于規(guī)則的知識表示和推導 翻譯規(guī)則（數(shù)據(jù)）與程序分離 翻譯程序體現(xiàn)為規(guī)則語言的解釋器！,翻譯的基本任務,源語言分析 詞法分析 句法分析 語義分析 轉換 不同層次 詞序、結構、語義的調整 譯詞選擇 目標語言生成 詞形變化 增/刪詞,自然語言的分類（基于形態(tài)結構）,分析型語言 詞形變化很少 沒有表示詞的語法功能的附加成分，由詞序和虛詞表示詞之間的語法關系 漢語、藏語等 黏著型語言 有詞形變化 詞的語法意義（功能）由附加成分表達 芬蘭語、日語等 屈折型語言 有詞形變化 詞的語法意義由詞的形態(tài)變化來表示 英語、德語、法語等 另外，還可以按SVO型（主動賓）、VSO型

19、（動主賓）和SOV 型(主賓動) 分類,詞法分析,形態(tài)還原（針對英語、德語、法語等） 把句子中的詞還原成基本詞形，作為詞的其它信息（詞典、個性規(guī)則）的索引。 詞性標注 為句子中的詞標上預定義類別集合（標注集）中的類。 分詞（針對漢語、日語等） 識別出句子中的詞。 命名實體識別 人名 地名 機構名,形態(tài)還原（英語）,構詞特點 屈折變化：詞尾和詞形變化，詞性不變。如： study, studied,studied,studying speak,spoke,spoken,speaking 派生變化：加前綴和后綴，詞性發(fā)生變化。如： friend,friendly,friendship,... 復合變

20、化：多個單詞以某種方式組合成一個詞。 還原規(guī)則 通用規(guī)則：變化有規(guī)律 個性規(guī)則：變化無規(guī)律,形態(tài)還原規(guī)則舉例,英語“規(guī)則動詞”還原 *s - * (SINGULAR3) *es - * (SINGULAR3) *ies - *y (SINGULAR3) *ing - * (VING) *ing - *e (VING) *ying - *ie (VING) *??ing - *? (VING) *ed - * (PAST)(VEN) *ed - *e (PAST)(VEN) *ied - *y (PAST)(VEN) *??ed - *? (PAST)(VEN),英語不規(guī)則動詞還原 went -

21、 go (PAST) gone - go (VEN) sat - sit (PAST) (VEN),形態(tài)還原算法,輸入一個單詞 如果詞典里有該詞，輸出該詞及其屬性，轉4，否則，轉3 如果有該詞的還原規(guī)則，并且，詞典里有還原后的詞，則輸出還原后的詞及其屬性，轉4，否則，調用 如果還有單詞，轉(1)，否則，結束。 Proj. 1 實現(xiàn)一個英語單詞還原工具。 （詞典：,詞性標注,為句子中的詞標上預定義類別集合（標注集）中的類，為后續(xù)的句法/語義分析提供必要的信息。 標注體系 標注方法,詞性標注體系,詞的分類 按形態(tài)和句法功能（句法相關性） 按表達的意思（語義相關性） 兼顧上述二者 為什么要分類？分類

22、帶來的問題？ 兼類詞 一個詞具有兩個或者兩個以上的詞性 英文的Brown語料庫中，10.4%的詞是兼類詞。例如： The back door On my back Promise to back the bill 漢語兼類詞，例如： 把門鎖上， 買了一把鎖 他研究...， 研究工作 漢語詞的兼類更多？與所采用的分類體系是否有關？,英語詞的分類,開放類（open class） Nouns 句法上：可有限定詞、可作物主、有復數(shù)形式 語義上：人名、地名和物名 Verbs 句法上：幾種詞形變化 語義上：動作、過程（一系列動作） Adjectives 句法上：修飾Nouns等 語義上：性質 Adverb

23、s 句法上：修飾Verbs等 語義上：方向、程度、方式、時間,封閉類（closed class，function words） Determiners Pronouns Prepositions Conjunctions Auxiliary verbs Particles Numerals,詞性標注方法,規(guī)則方法 詞典和規(guī)則提供候選詞性 消歧規(guī)則進行消歧 統(tǒng)計方法 選擇最可能的標注 訓練用語料庫（已標注） HMM標注等方法 基于轉換學習的方法 統(tǒng)計學習規(guī)則 用規(guī)則方法進行標注,漢語分詞（切分）,詞是語言中最小的能獨立運用的單位，也是語言信息處理的基本單位。 分詞是指根據(jù)某個分詞規(guī)范，把一個“字

24、”串分成“詞”串。 分詞規(guī)范 難以確定何謂漢語的“詞” 單字詞與語素的界定：豬肉、牛肉 詞與短語（詞組）的界定：黑板、黑布 信息處理用現(xiàn)代漢語分詞規(guī)范：GB-13715（1992） 具體系統(tǒng)可根據(jù)各自的需求制定規(guī)范,分詞方法,一般通過分詞詞典和分詞規(guī)則庫進行分詞。主要方法有： 正向最大匹配(FMM)或逆向最大匹配(RMM) 從左至右(FMM)或從右至左(RMM)，取最長的詞 會忽略“詞中有詞”的現(xiàn)象：“幼兒園 地 節(jié)目” 雙向最大匹配 分別采用FMM和RMM進行分詞 如果結果一致，則認為成功；否則， 采用消歧規(guī)則進行消歧（交集型歧義）： 正向最大、逆向最小匹配 發(fā)現(xiàn)組合型歧義 逐詞遍歷匹配 在

25、全句中取最長的詞，去掉之，對剩下字符串重復該過程 設立切分標記 收集詞首字和詞尾字，把句子分成較小單位，再用某些方法切分 全切分 獲得所有可能的切分，選擇最大可能的切分,切分歧義及歧義字段的種類,交集型歧義字段 ABC切分成AB/C或A/BC 如：“和平等” “獨立/自主/和/平等/獨立/的/原則” “討論/戰(zhàn)爭/與/和平/等/問題” 組合型歧義字段 AB切分成AB或A/B 如：“馬上” “他/騎/在/馬/上” “馬上/過來” 混合型歧義 由交集型歧義和組合型歧義嵌套與交叉而成 如：“太平、太平淡” “這/篇/文章/寫/得/太/平淡/了” “這/墻/抹/得/太/平/了” “即使/太平/時期/也

26、/不/應該/放松/警惕”,南京市長江大橋...,南京市長江二橋...,偽歧義與真歧義 偽歧義字段指在任何情況下只有一種切分 “為人民”只有一種切分：“為/人民”，如：“為/人民/服務” 根據(jù)歧義字段本身就能消歧 真歧義字段指在不同的情況下有多種切分 “從小學”可以有多種切分： “從小/學” ，如：“從小/學/電腦” （“從小”是切分成“從小”還是“從/小”要根據(jù)分詞規(guī)范?。?“從/小學”，如：“他/從/小學/畢業(yè)/后” 根據(jù)歧義字段的上下文來消歧,基于規(guī)則的歧義字段消歧方法,利用歧義字串、前驅字串和后繼字串的句法、語義和語用信息： 句法信息 “陣風”：根據(jù)前面是否有數(shù)詞來消歧?！耙?陣/風/吹

27、/過/來”、“今天/有/陣風” 語義信息 “了解”：“他/學會/了/解/數(shù)學/難題”（“難題”一般是“解”而不是“了解”) 語用信息 “拍賣”：“乒乓球拍賣完了”，要根據(jù)場景（上下文）來確定 規(guī)則的粒度 基于詞（個性規(guī)則） 基于詞類、詞義（共性規(guī)則） Proj. 2 實現(xiàn)一個基于詞典與規(guī)則的漢語自動分詞系統(tǒng)。 (詞典：,基于詞的轉換翻譯,翻譯過程 譯詞選擇 詞序調整 形態(tài)（詞形變化）生成 翻譯所基于的知識 對譯（雙語）詞典及規(guī)則 調序規(guī)則 形態(tài)生成規(guī)則 問題 沒有句法結構和語義分析的指導，轉換很難很好地進行，特別是對句法/語義結構相差很大的語言。 譯詞選擇和詞序調整工作可用的信息太少（利用原句

28、中的局部信息和已得到的譯詞信息） 。,句法分析（Parsing）,句法分析的目的 判斷句子的合法性（句子識別） 確定句子的結構（句子中單詞相互關聯(lián)的方式） 從機器翻譯角度：比詞一級的轉換提供更多的信息 基于上下文無關語法（CFG）的表示 CFG能描述大部分的自然語言結構 可以構造高效的基于CFG的句法分析器 通常采用樹形結構來表示句法分析的結果,一個簡單的產(chǎn)生式語法（英語）,1. S - NP VP 2. VP - V NP 3. NP - NAME 4. NP - ART N 5. NAME - John 6. V - ate 7. ART - the 8. N - cat 9. .....

29、. 產(chǎn)生式59屬于詞法規(guī)則，一般由詞典與詞性標注算法來描述,John ate the cat的句法分析結果,,,,,,,,,,,,S,NP,VP,NAME,John,V,NP,ate,ART,N,the,cat,優(yōu)秀語法的特征,通用性 能正確分析句子的范圍 選擇性 能判斷出錯誤句子的范圍 可理解性 自身的簡易程度 *魯棒性 對不合法句子的容忍度：He love her. 通用性與選擇性矛盾的處置，如：忽略主謂一致性檢查將導致無法區(qū)分下面句子的不同含義（歧義） Flying planes are dangerous. Flying planes is dangerous.,基于產(chǎn)生式的CFG分析

30、器,自頂向下 利用產(chǎn)生式，從S開始，嘗試將S改寫/推導成與輸入句子相匹配的終結符號序列。 自底向上 利用產(chǎn)生式，嘗試將輸入句子規(guī)約到S。 回溯 從一個錯誤的嘗試（改寫或規(guī)約）返回，進行下一個嘗試。 保留改寫或規(guī)約的歷史 回溯需要 輸出正確的分析結果也需要,一個簡單的自頂向下句法分析算法,語法 1. S - NP VP 2. NP - ART N 3. NP - ART ADJ N 4. VP - V 5. VP - V NP 位置計數(shù)器 1 The 2 dogs 3 cried 4 狀態(tài) 由符號表和當前位置構成，如：((NP VP) 1) 表示從位置1開始尋找NP，且NP后面是VP。

31、初始狀態(tài)為：((S) 1) 狀態(tài)轉換 如果符號表的第一個符號是詞法符號（詞性），并且句子中當前詞屬于該詞法類，則刪除符號表中第一個符號，并更新當前位置(加1)，得到新的狀態(tài)。 否則，如果符號表的第一個符號是句法符號，則依據(jù)語法獲得改寫該符號的所有產(chǎn)生式，把它們的右部作為符號表與當前位置構成狀態(tài)；選擇其中一個作為新的狀態(tài)，其它作為后備狀態(tài)（在回溯時使用）。 回溯 從后備狀態(tài)中取一個作為當前狀態(tài)，繼續(xù)分析,算法 1. 取 ((S) 1)作為當前狀態(tài)（初始狀態(tài)），后備狀態(tài)為空。 2. 若當前狀態(tài)為空，則失敗，算法結束， 3. 否則，若當前狀態(tài)符號表為空， (1)當前位置處于句子末尾，則成功，算法結束

32、 (2)當前位置處于句子中間，轉5 4. 否則，進行狀態(tài)轉換，若轉換成功，則轉2 5. 否則，回溯，轉2。,,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程（續(xù)）,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,搜索策略,深度優(yōu)先 后備狀態(tài)采用“?！?后備狀態(tài)少，存儲效率高 面臨“左遞歸”問題

33、廣度優(yōu)先 后備狀態(tài)采用“隊列” 后備狀態(tài)多，存儲效率不高,基于圖的自底向上句法分析(chart parsing),簡單的自底向上句法分析效率不高，常常會重復嘗試相同的匹配操作（回溯之前已匹配過）。 一種基于圖的句法分析，采用一個數(shù)據(jù)結構來存儲已經(jīng)匹配過的結果，今后需要時可直接使用它們，不必重新匹配。（動態(tài)規(guī)劃） 圖的構成 結點表示句子中詞之間的位置數(shù)字 邊分為：非活動邊和活動邊 非活動邊：已匹配的詞法符號或句法符號 活動邊：未完全匹配的產(chǎn)生式，用加小圓圈標記（）的產(chǎn)生式來表示，如： NP - ART ADJ N NP - ART N,Chart Parsing句法分析算法,chart（非活動邊

34、） 記錄分析中規(guī)約成功所得到的所有詞法和句法符號 activearcs（活動邊集） 記錄活動邊 agenda（待處理表） 記錄等待加入chart的匹配成功的詞法和句法符號 上面的活動邊、非活動邊以及詞法和句法符號都帶有“始/終結點號”,重復下面的操作直到agenda為空并且輸入中沒有下一個詞 若agenda為空，則把句子中下一個詞的各種詞法符號（詞性）加入進來， 從agenda中取一個元素（設為C，位置為：p1-p2) 對下面形式的每個規(guī)則： X-CX1...Xn，在activearcs中增加一條活動邊：X-C X1...Xn，位置為：p1-p2； X-C，把X加入agenda，位置為：p1-

35、p2 邊擴展 將C加入到chart的位置p1-p2 對每個形式為：X-X1... C...Xn的活動邊，若它在p0-p1之間，則在activearcs中增加一條活動邊：X-X1... C ...Xn，位置:p0-p2 對每個形式為： X-X1... Xn C的活動邊，若它在p0-p1之間，則在agenda中增加一個成分：X，位置為：p0-p2,Chart Parsing句法分析算法（續(xù)）,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程 (算法),1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART A

36、DJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,ART(1,2),agenda,5,6,a,mouse,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程 (算法),1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,N(2,3),agenda,5,6,

37、a,mouse,,,,N,NP(1,3),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程 (算法),1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mouse,,,,N,NP(1,3),,,S - NP VP,,,,NP,,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4

38、,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mouse,,,,N,V(3,4),,,S - NP VP,,,,NP,,,,,VP - V NP,VP(3,4),,,V,,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART A

39、DJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mouse,,,,N,,,S - NP VP,,,,NP,,,,,VP - V NP,VP(3,4),,,V,,,,VP,,S(1,4),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-A

40、RT ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mouse,,,,N,,,S - NP VP,,,,NP,,,,,VP - V NP,,,V,,,,VP,,S(1,4),,,S,,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mou

41、se,,,,N,,,S - NP VP,,,,NP,,,,,VP - V NP,,,V,,,,VP,,ART(4,5),,,S,,,,,NP - ART N,,,NP - ART ADJ N,,,,ART,,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mouse,,,,

42、N,,,S - NP VP,,,,NP,,,,,VP - V NP,,,V,,,,VP,,N(5,6),,,S,,,,,NP - ART N,,,NP - ART ADJ N,,,,ART,,,,N,,NP(4,6),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mous

43、e,,,,N,,,S - NP VP,,,,NP,,,,,VP - V NP,,,V,,,,VP,,,,S,,,,,NP - ART N,,,NP - ART ADJ N,,,,ART,,,,N,,NP(4,6),,,S - NP VP,,,,NP,,VP(3,6),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-

44、V NP,,,,agenda,5,6,a,mouse,,,,N,,,S - NP VP,,,,NP,,,,,VP - V NP,,,V,,,,VP,,,,S,,,,,NP - ART N,,,NP - ART ADJ N,,,,ART,,,,N,,,,S - NP VP,,,,NP,,VP(3,6),,,VP,,S(1,6),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程,1,2,3,4,,,,The,cat,caught,ART,,,,NP - ART N,,,,NP - ART ADJ N,活動邊,非活動邊,1. S-NP VP 2. NP-ART N

45、3. NP-ART ADJ N 4. VP-V 5. VP-V NP,,,,agenda,5,6,a,mouse,,,,N,,,S - NP VP,,,,NP,,,,,VP - V NP,,,V,,,,VP,,,,S,,,,,NP - ART N,,,NP - ART ADJ N,,,,ART,,,,N,,,,S - NP VP,,,,NP,,,,VP,,S(1,6),,,S,,,Proj. 3 實現(xiàn)一個基于簡單英語語法的chart句法分析器。,基于遞歸轉移網(wǎng)絡的語法表示,除了CFG的產(chǎn)生式規(guī)則外，遞歸轉移網(wǎng)絡（Recusive Transition Network，簡稱RTN）是另一種表示自

46、然語言語法的形式化手段。 一個RTN是由結點和有向邊組成： 結點表示狀態(tài)，起始狀態(tài)對應于產(chǎn)生式規(guī)則中的一個句法符號。 有向邊可以是以下類型： CAT：詞法符號（詞性） WRD：詞 PUSH（句法符號）：轉向其它轉移網(wǎng)絡的名 POP：成功結束當前網(wǎng)絡 JUMP：無條件轉移 一個RTN相當于一個不確定的下推自動機,一個基于RTN的英語語法表示,NP,NP1,NP2,NP：,ART,N,pop,ADJ,S,S1,NP（push）,V,NP,S2,S:,pop,PRON,NUM,1,2,3,1,2,1,2,返回,基于RTN的自頂向下句法分析,狀態(tài) (當前結點,當前輸入位置,返回結點棧) 起始狀態(tài) (S

47、,1,NIL) 終止狀態(tài) (NIL,n,NIL) n為句子的終止位置 后備狀態(tài) 回溯,狀態(tài)轉換 按下面滿足條件的邊進行轉換，若有多個滿足條件的邊，則選其中一條邊的轉換結果作為新的當前狀態(tài)，其它邊的轉換結果作為后備狀態(tài)。 如果當前邊為詞類（詞法符號）并且句子中下一個詞屬于該詞類 更新輸入位置（+1） 更新當前結點為當前邊的目標結點 如果當前邊為PUSH（設為句法符號N） 將當前邊的目標結點加入返回結點棧 更新當前結點為N的起始結點 如果當前邊是POP且返回結點棧非空 取返回結點棧元素作為當前結點 如果當前邊是POP、返回結點棧為空且句子沒有剩余的詞 句法分析成功 回溯 后備狀態(tài)不為空，從中取一個

48、，繼續(xù)進行前面的轉換 否則，失敗,句子“1One 2saw 3the 4man 5”的分析過程,,句法分析與邏輯程序設計,邏輯程序設計是把程序組織成一組事實和一組推理規(guī)則，它基于謂詞演算（Predicate Calculus）進行計算，計算過程由實現(xiàn)系統(tǒng)給出。 可以把語法寫成PROLOG的事實（公理）和子句（規(guī)則）形式（由謂詞構成），推理過程由PROLOG的執(zhí)行機制自動完成。,一個CFG語法的PROLOG表示,語法規(guī)則可表示成： s(P1,P3):-np(P1,P2),vp(P2,P3) np(P1,P3):-art(P1,P2),n(P2,P3) np(P1,P3):-name(P1,P3)

49、 pp(P1,P3):-p(P1,P2),np(P2,P3) vp(P1,P2):-v(P1,P2) vp(P1,P3):-v(P1,P2),np(P2,P3) vp(P1,P3):-v(P1,P2),pp(P2,P3) n(P1,P2):-word(W,P1,P2),isnoun(W) art(P1,P2):-word(W,P1,P2),isart(W) v(P1,P2):-word(W,P1,P2),isverb(W) name(P1,P2):-word(W,P1,P2),isname(W),詞典可表示成： isart(the) isname(john) isverb(ate) isnou

50、n(cat) ......,輸入句子“John ate the cat”可表示成： word(john,1,2) word(ate,2,3) word(the,3,4) word(cat,4,5) 通過查詢謂詞s(1,5)的真假來識別句子“John ate the cat”： ?- s(1,5) 標準PROLOG的搜索策略與自頂向下的深度優(yōu)先分析方法一致。,CFG在描述自然語言時存在的問題,1. S - NP VP 4. VP - V 2. NP - ART N 5. VP - V NP 3. NP - ART ADJ N 上面的語法描述了英語的一個子集，同時，它又會生成一些不合

51、法的英語句子，如： The student solve the problem The teacher disappeared the problem,一種可能的解決方案增加句法符號,把NP分為NP-S和NP-P；把VP分成VP-S和VP-P： S-NP-S VP-S S-NP-P VP-P 把N分成N-S和N-P： NP-S-ART N-S NP-S-ART ADJ N-S NP-P-ART N-P NP-P-ART ADJ N-P 把V分成V-S-I、V-S-T、V-P-I和V-P-T： VP-S-V-S-I VP-S-V-S-T NP-S VP-S-V-S-T NP-P VP-P-V-P

52、-I VP-P-V-P-T NP-S VP-P-V-P-T NP-P,增加句法符號帶來的問題,增加了規(guī)則的數(shù)量和潛在的冗余 類似的規(guī)則缺乏關聯(lián)性 對語言結構描述缺乏深度,基于特征的擴展CFG,不增加原CFG中的句法符號 給每個句法符號增加特征，例如： NP(PER 3,NUM s) VP(PER 3,NUM s,VAL itr) 特征由特征名和特征值構成。一系列特征構成了一個特征結構（復雜特征集）。 特征值可以是普通值（原子），也可以是另一個特征結構，例如： NP(AGR （PER 3, NUM s)) 簡寫為： NP(AGR 3s) 一個特征的特征值可以有多個，表示成： N(ROOT fis

53、h, AGR 3s,3p),特征值也可以是變量，例如： NP(AGR ?a) S-NP(AGR ?a) VP(AGR ?a) 表示NP與VP的AGR特征值一致 一個規(guī)則如果包含特征值為變量的成分，則該規(guī)則代表了一組規(guī)則。 可以對變量形式的特征值限定范圍（受限變量），例如： NP(AGR ?a3s,3p),一個基于特征結構的CFG語法,S-NP(AGR ?a) VP(AGR ?a) NP(AGR ?a) - ART N(AGR ?a) NP(AGR ?a) - ART ADJ N(AGR ?a) VP(AGR ?a) - V(AGR ?a,VAL itr) VP(AGR ?a) - V(AGR

54、?a,VAL tr) NP,基于特征CFG的chart parsing,句子語法成分與規(guī)則匹配時，要對各個特征進行匹配和泛化處理。 若規(guī)則包含特征值為變量的成分，匹配時需要實例化這個規(guī)則，例如： 對于規(guī)則： NP(AGR ?a)- ART(AGR ?a) N(AGR ?a) 若有下面的語法成分需要匹配： ART(ROOT a, AGR 3s) 則需要實例化規(guī)則中的?a： NP(AGR 3s)- ART(AGR 3s) N(AGR 3s) 它與ART(ROOT a, AGR 3s)匹配后擴展為： NP(AGR 3s)- ART(AGR 3s) N(AGR 3s) 若句子中還有N(ROOT dog

55、, AGR 3s)需要匹配，則進一步擴展為： NP(AGR 3s)- ART(AGR 3s) N(AGR 3s) ,如果待匹配的語法成分的特征值中包含受限變量，則實例化后的規(guī)則中的取值范圍為兩者的交集，例如： 實例化前的規(guī)則： NP(AGR ?a)- ART(AGR ?a) N(AGR ?a) 要匹配的語法成分： ART(ROOT the, AGR ?a3s,3p) 實例化后的規(guī)則為： NP(AGR ?a3s,3p)- ART(AGR ?a3s,3p) N(AGR ?a3s,3p) 匹配擴展后為： NP(AGR ?a3s,3p)- ART(AGR ?a3s,3p) N(AGR ?a3s,3p)

56、 再與N(ROOT dog, AGR 3s)匹配后擴展為： NP(AGR 3s)- ART(AGR 3s) N(AGR 3s) ,擴充的轉移網(wǎng)絡（ATN）,把特征加入遞歸轉移網(wǎng)絡（RTN）就得到了擴充轉移網(wǎng)絡（Augmented Transition Network, ATN）。 特征用寄存器表示。 一個網(wǎng)絡可以包含一組特征寄存器（特征變量） 當前待匹配的語法成分也包含一組特征寄存器 在ATN中，通過一條邊時，需要： 判斷網(wǎng)絡當前特征寄存器的值與當前待匹配的語法成分的特征寄存器的值是否一致（測試） 計算網(wǎng)絡特征寄存器新的當前值（動作）,一個簡單NP的ATN,NP,NP1,NP2,NP：,ART

57、,N,pop,NAME,1,3,2,特征寄存器：DET、AGR、HEAD、NAME、...,一個簡單S的ATN,S,S1,NP,V,S2,S:,NP,3,S2,pop,2,1,特征寄存器：SUBJ、MAIN-V、AGR、OBJ、...,“1The 2dog 3saw 4Jack5”的測試與動作的處理流程,跟蹤網(wǎng)絡S,第一次跟蹤網(wǎng)絡NP,第二次跟蹤網(wǎng)絡NP,“1The 2dog 3saw 4Jack5”的測試與動作的處理流程（續(xù)）,基于合一的語法,一個文法可以表示成一系列特征結構間的約束關系所組成的集合。這樣的文法稱為合一文法（Unification Grammar）。例如： 特征結構X0、X1

58、和X2之間的約束關系： X0-X1 X2 (CAT0=S,CAT1=NP,CAT2=VP, AGR0=AGR1=AGR2,VFORM0=VFORM2) 它描述了基于特征的CFG中的一條規(guī)則： S-NP(AGR ?a) VP(AGR ?a) 合一文法為其它的基于特征的文法提供了一個形式描述基礎 特征結構的合一運算構成了合一文法的基本操作，其作用有兩個： 創(chuàng)建新的特征結構（規(guī)約的結果） 檢查特征結構間的相容性以確定多個特征結構是否可以合并（規(guī)約）,合一運算,復雜特征集相容 (f)表示復雜特征集的特征f的值 若、為復雜特征集，則和相容，當且僅當： 若(f)=a，(f)=b，a、b都是原子，

59、和是相容的當且僅當a=b 若(f)、(f)均為復雜特征集，和是相容的當且僅當(f)與(f)相容 復雜特征集合一運算： 如果a、b都是原子,若a=b，則ab=a，否則ab= 若、均為復雜特征集，則 若(f)=v，但(f)未定義，則f=v屬于 若(f)=v，但(f)未定義，則f=v屬于 若(f)=v1，(f)=v2，且v1與v2相容，則f=(v1v2)屬于，否則，= ,合一運算舉例,(CAT V, ROOT cry)與(CAT V, VFORM pres) 可以合一為：(CAT V, ROOT cry, VFORM pres) (CAT V, AGR 3s)與(CAT V, AGR 3p)不能合一

60、 (CAT N,ROOT fish, AGR 3s,3p)與(CAT N, AGR 3s) 可以合一為： (CAT N,ROOT fish, AGR 3s),基于句法結構轉換的翻譯,遞歸地利用一組“樹-樹”的轉換規(guī)則，把源語言的分析樹轉換成目標語言分析樹，然后生成目標語言句子。,句法樹轉換的例,NP,,,Det,A,,N1,,,delicious,soup,,Adj,N,,NP,,,NP,,,tv(X),tv(Y),tv(X),tv(Y),NP,,,Det,Una,,N1,,,sopa,deliciosa,,N,Adj,,,,N1,,,tv(A),tv(B),,Adj,N,,N1,,,tv(B

61、),tv(A),,N,Adj,,,,Det,Una,,,SL Tree,Tree-to-tree transformations,TL Tree,,delicious deliciosa soup sopa,Det,A,,A delicious soup,Una sopa deliciosa,(English),(Spanish),基于句法結構轉換翻譯面臨的問題,翻譯發(fā)散（Translation divergence） 兩種語言在表達同一個意思的句法結構和語義分布上存在差別 翻譯失配（Translation mismatch） 兩種語言在概念表達方面存在差別（不存在直譯）,翻譯發(fā)散的種類,論

62、旨發(fā)散（Thematic） 句子成分的語法作用發(fā)生變化，例如： En: You like her. Sp: Ella te gusta.(She you-ACC pleases) 賓語(her)變成主語(Ella) 中心語換位（Head Switching） 句法單位的中心詞發(fā)生變化，例如： En: The baby just ate. Sp: El bebe acaba de comer.(The baby finished of to-eat) 動詞(ate)變成補足語(comer),結構發(fā)散（Structural） 例如： En: Luisa entered the house. Sp:

63、 Luisa entro a la casa.(Luisa entered to the house) V+NP 變成 V+PP 詞匯差別（Lexical Gap） 一個詞變成幾個詞，例如： En: Camilo got up early. Sp: Camilo madrugo. get up early 變成 madrugo,語義的詞匯表現(xiàn)（Lexicalization） 例如： En: Susan swam across the channel. Sp: Susan cruzo el canal nadando.(Susan crossed the channel swimming) “運

64、動/方式途徑”變成“運動/途徑方式” 詞法類別（Categorial） 例如： En: A little bread. Sp: Un poca de pan.(A bit of bread) 形容詞變成名詞,搭配（Collocational） 例如： En: Jan made a decision. Sp: Jan tomo una decision. made的原意翻譯為：hacer，但與decision搭配時應翻譯成tomo 多詞位和成語（Multi-lexeme and Idiomatic） 成語，例如： En: Socrates kicked the bucket.(Socrates死

65、了） Sp: Socrates estiro la pata.(Socrates stretched the leg) 多詞位，例如： En: Frank is as tall as Orlaith. Sp: Frank es tan alto como Orlaith.,句義分析,句法層的轉換有時很困難（特別是在句子結構相差很大的語言之間），這時，需要到語義層進行轉換。 句義分析的目的是給出句子的含義或意義(meaning)。句子的意義分為： 上下文無關意義 上下文有關意義 “Do you know what gate you are going to?”的意義是什么？ 句義分析的作用： 更

66、好地進行翻譯：Tom ran the machine. 句法結構消歧：I saw a boy with a telescope. 句義分析的方式 先句法后語義 句法語義一體化 完全語義分析（無句法分析）,詞匯語義,句子的意義由句子中詞匯的語義組合而成。 句義分析首先需要解決詞匯的語義表示和分析。 詞匯的語義表示： 義項（義位） 語義類 義素組合,義項（義位）,一個詞往往有幾個意義，每一個意義就是一個義項。例如：“明白”在現(xiàn)代漢語詞典中的義項： 內容、意義等使人容易了解；清楚；明確 公開的、不含糊的 聰明；懂道理 知道；了解 義項之間的關系 上下位關系： “動物”與 “獅子” 整體-部分關系：“身體”與“上肢” 同義關系：“美麗”與“漂亮” 反義關系：“高”與“矮” 包含關系：“兄弟”與“哥哥”和“弟弟” 義項之間的關系可以為義項之間的搭配提供依據(jù)，從而為詞義消歧（義項選擇）和句義分析提供幫助。,語義場,表示義項之間關系的另一種方式是語義場由幾個相互關聯(lián)的義項構成的語義系統(tǒng)。例如： “師傅、徒弟”構成一個語義場 “上、下、左、右”也構成一個語義場 語義場的確定與本體論（Ontology）