機器翻譯理論和技術 - 計算機系主頁

1、自然語言處理Natural Language Processing(NLP),陳家駿，戴新宇chenjj@nlp.nju.edu.cndxy@nlp.nju.edu.cn,主要內容（1）,自然語言處理概述什么是自然語言處理自然語言處理技術的應用自然語言處理的基本策略和實現方法自然語言處理的難點自然語言處理所涉及的學科(http://cs.nju.edu.cn/chenjiajun/nlp_traditional.pp

2、t),基于規(guī)則的自然語言處理方法（理性方法，傳統(tǒng)方法）基于詞典和規(guī)則的形態(tài)還原（英語）、詞性標注以及分詞（漢語、日語）基于CFG（上下文無關文法）和擴充的CFG（復雜特征集、合一運算）的句法表示及其分析技術基于邏輯形式和格語法的句義分析基于規(guī)則的機器翻譯(http://cs.nju.edu.cn/chenjiajun/nlp_traditional.ppt),主要內容（2）,基于語料庫的自然語言處理方法（經驗方法）語言模型

3、（N元文法）分詞、詞性標注（序列化標注模型）句法分析（概率上下文無關模型）文本分類（樸素貝葉斯模型、最大熵模型）機器翻譯 (IBM Model等)......（基于神經網絡的深度學習方法）,主要內容（3）,所需的前導知識,編譯技術概率與統(tǒng)計,參考書籍,宗成慶，統(tǒng)計自然語言處理，清華大學出版社，2008劉群等譯，自然語言理解（第二版），電子工業(yè)出版社，2005苑春法等譯，統(tǒng)計自然語言處理基礎，電子工業(yè)出版社，2005馮志

4、偉等譯，自然語言處理綜論，電子工業(yè)出版社，2005黃昌寧等，語料庫語言學，商務印書館，2002馮志偉，計算語言學基礎，商務印書館，2001余士文，計算語言學概論，商務印書館，2003姚天順，自然語言理解－－一種讓機器懂得人類語言的研究（第2版），清華大學出版社，2002趙鐵軍等，機器翻譯原理，哈爾濱工業(yè)大學出版社，2000宗成慶等譯，統(tǒng)計機器翻譯，電子工業(yè)出版社，2012Peter F. Brown, et al., A

5、Statistical Approach to MT, Computational Linguistics, 1990,16(2),課程考核,Projects提交報告（說明基本做法）和源程序及可運行的程序期末筆試,,自然語言處理概述,什么是自然語言處理,充分利用信息將會給人們帶來巨大的收益，而大量的信息以自然語言（英語、漢語等）形式存在。如何有效地獲取和利用以自然語言形式出現的信息？自然語言處理（Natural Language

6、 Processing，簡稱NLP）是指用計算機對語言信息進行處理的方法和技術。與NLP相近的兩個研究領域：自然語言理解(Natural Language Understanding, NLU)：強調對語言含義和意圖的深層次解釋計算語言學(Computational Linguistics, CL)：強調可計算的語言理論,NLP技術的應用,機器翻譯自動摘要文本分類與信息過濾信息檢索信息抽取與文本挖掘情感分析自動問答.

7、.....,機器翻譯（Machine Translation）,機器翻譯（Machine Translation，簡稱MT）是指利用計算機實現自然語言（英語、漢語等）之間的自動翻譯。是最早的計算機應用之一分為：文本機器翻譯和語音機器翻譯機器輔助翻譯（Machine Aided Translation或Computer Aided Translation，簡稱MAT或CAT）翻譯記憶體（Translation Memory，簡稱T

8、M）雙語對照的文本編輯...,自動摘要（Text Summarization）,利用計算機自動地從原始文檔中提取全面準確地反映該文檔中心內容的簡潔、連貫的短文。指標：壓縮比、...,文本分類（Text Classification）,將一篇文檔歸于預先給定的一個類別集合中的某一類或某幾類?？捎糜趫D書館的圖書分類信息過濾......,信息檢索（Information Retrieval，IR）,主題相關的文本獲取?；陉P鍵

9、詞，從某文檔集合中檢索出相關的文檔。關鍵技術：倒排索引、...google、百度、...,信息抽取（Information Extraction，IE）,主題相關的信息獲取?；谀硞€主題模板，從非結構化或半結構化的自然語言文本中提取出相關的結構化信息。對機器翻譯、自動問答、數據挖掘（文本挖掘）等提供支持。,新華社北京３月８日電（記者李術峰）: 中國農工民主黨第十二屆中央常務委員會第一次會議今天在北京召開。會議研究通過了貫徹落實

10、“兩會”精神的有關決定，審議通過了中國農工民主黨中央１９９８年工作要點（草案），并任命了中央副秘書長。農工民主黨中央主席蔣正華主持了會議，他說，農工民主黨有１００多名黨員作為代表和委員參加了今年的“兩會”，各位黨員要認真履行代表和委員的職責，開好會，在１９９８年的工作中認真貫徹“兩會”精神，加強農工民主黨的自身建設，推動事業(yè)進一步發(fā)展，為建設有中國特色社會主義事業(yè)作出新的貢獻。會前，農工民主黨中央邀請參加“兩會”的來自全國各省、自治

11、區(qū)、直轄市的農工民主黨黨員進行了聯誼活動。,信息抽取實例:會議報道(人民日報1998-03-09),信息抽取的結果,情感分析（Sentiment Analysis或 Opinion Analysis ）,分析文章（評論）對某個對象（社會熱點事件、產品或者服務）的態(tài)度（正面還是負面）。政府輿情分析：熱點事件發(fā)現、預警企業(yè)市場決策：產品意見調查、產品推薦消費者購買決策......,自動問答（Question Answering，QA

12、）,針對用戶提出的問題，給出具體的答案。Apple的Siri、IBM的Watson機器人、百度的“知道”、…,自然語言處理的主要任務（工作）,語言分析：分析語言表達的結構和含義詞法分析：形態(tài)還原、詞性標注、命名實體識別、分詞（漢語、日語等）等句法分析：組塊分析、結構分析、依存分析語義分析：詞義、句義（邏輯、格關系、...）、篇章（上下文）（指代、實體關系）語言生成：從某種內部表示生成語言表達多語言處理（機器翻譯、跨語言檢索）

13、：語言之間的對應、轉換不同的應用對上述任務有不同的要求。,自然語言的分類（基于形態(tài)結構）,分析型語言詞形變化很少沒有表示詞的語法功能的附加成分，由詞序和虛詞表示詞之間的語法關系漢語、藏語等黏著型語言有詞形變化詞的語法意義（功能）由附加成分表達日語、芬蘭語等屈折型語言有詞形變化詞的語法意義由詞的形態(tài)變化來表示英語、德語、法語等另外，還可以按SVO型（主－動－賓）、VSO型（動－主－賓）和SOV 型(主－賓－動)

14、分類,自然語言處理的實現方法,基于規(guī)則的理性方法（Rationalist approach）基于以規(guī)則形式表達的語言知識（詞、句法、語義以及轉換、生成）進行推理。強調人對語言知識的理性整理。受Chomsky主張的人具有先天語言能力觀點的影響，主宰1960－1985基于語料庫的經驗方法（Empiricist approach）以大規(guī)模語料庫（單語和雙語）為語言知識基礎。利用統(tǒng)計學習和基于神經網絡的深度學習方法自動獲取和運用隱含

15、在語料庫中的知識。學習到的知識體現為一系列模型參數。,混合方法理性方法的優(yōu)、缺點相應的語言學理論基礎好語言知識描述精確處理效率高知識獲取困難（高級勞動）系統(tǒng)魯棒性（適應性）差：不完備的規(guī)則系統(tǒng)將導致推理的失敗知識擴充困難，很難保證規(guī)則之間的一致性經驗方法的優(yōu)、缺點知識獲取容易（低級勞動）系統(tǒng)魯棒性好：概率大的作為結果知識擴充容易、一致性容易維護相應的語言學理論基礎差缺乏對語言學知識的深入描述和利用，過于機械

16、處理效率低利用各家之長，相互融合,自然語言處理的難點,歧義處理有限的詞匯和規(guī)則表達復雜、多樣的對象語言知識的表示、獲取和運用成語和慣用型的處理對語言的靈活性和動態(tài)性的處理靈活性：同一個意圖的不同表達，甚至包含錯誤的語法等動態(tài)性：語言在不斷的變化，如：新詞等上下文和世界知識（常識，語言無關）的利用和處理,漢語處理的難點,缺乏計算語言學的句法/語義理論，大都借用基于西方語言的句法/語義理論詞法分析分詞詞性標注難句法分

17、析主動詞識別難詞法分類與句法功能對應差語義分析句法結構與句義對應差時體態(tài)確定難 （漢語無形態(tài)變化）資源（語料庫）缺乏,自然語言處理所涉及的學科,計算語言學：各種語法、語義理論計算機科學（包括人工智能、機器學習）數學：邏輯、概率與統(tǒng)計、信息論等哲學（認知學）心理學......,,基于規(guī)則的自然語言處理方法 （理性方法，傳統(tǒng)方法）,概述,強調對語言知識的理性整理（知識工程）受計算語言學理論指導基于規(guī)則的知識表

18、示和推導（符號計算）語言處理規(guī)則（數據）與程序分離，程序體現為規(guī)則語言的解釋器！,詞法分析,形態(tài)還原（針對英語、德語、法語等）把句子中的詞還原成基本詞形。詞性標注為句子中的詞標上預定義類別集合（標注集）中的類。命名實體識別人名地名機構名分詞（針對漢語、日語等）識別出句子中的詞。,形態(tài)還原（英語）,把句子中的詞還原成原形，作為詞的其它信息（詞典、個性規(guī)則）的索引。構詞特點屈折變化：詞尾和詞形變化，詞性不變。如：s

19、tudy, studied,studied,studyingspeak,spoke,spoken,speaking派生變化：加前綴和后綴，詞性發(fā)生變化。如：friend,friendly,friendship,...復合變化：多個單詞以某種方式組合成一個詞。還原規(guī)則通用規(guī)則：變化有規(guī)律個性規(guī)則：變化無規(guī)律,形態(tài)還原規(guī)則舉例,英語“規(guī)則動詞”還原*s -> * (SINGULAR3)*es -> * (SIN

20、GULAR3)*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)(VE

21、N),英語不規(guī)則動詞還原went -> go (PAST)gone -> go (VEN)sat -> sit (PAST) (VEN),形態(tài)還原算法,輸入一個單詞如果詞典里有該詞，輸出該詞及其屬性，轉4，否則，轉3如果有該詞的還原規(guī)則，并且，詞典里有還原后的詞，則輸出還原后的詞及其屬性，轉4，否則，調用如果輸入中還有單詞，轉(1)，否則，結束。Proj. 1 實現一個英語單詞還原工具。（詞典：htt

22、p://nlp.nju.edu.cn/MT_Lecture/dic_ec.rar）,詞性標注,為句子中的詞標上預定義類別集合（標注集）中的類（詞性），為后續(xù)的句法/語義分析提供必要的信息。標注體系的確定標注方法,詞性標注體系,詞的分類按形態(tài)和句法功能（句法相關性）按表達的意思（語義相關性）兼顧上述二者,英語詞的分類,開放類（open class）Nouns句法上：可作物主、可有限定詞、有復數形式語義上：人名、地名和物名

23、Verbs句法上：作謂語、有幾種詞形變化語義上：動作、過程（一系列動作）Adjectives句法上：修飾Nouns等語義上：性質Adverbs句法上：修飾Verbs等語義上：方向、程度、方式、時間,封閉類（closed class，function words）DeterminersPronounsPrepositionsConjunctionsAuxiliary verbsParticles（if、not、

24、...）Numerals,,為什么要分類？分類帶來的問題？兼類詞一個詞具有兩個或者兩個以上的詞性英文的Brown語料庫中，10.4%的詞是兼類詞。例如：The back doorOn my backPromise to back the bill漢語兼類詞，例如：把門鎖上， 買了一把鎖他研究...， 研究工作漢語詞的兼類更多？與所采用的分類體系是否有關？,詞性標注方法,規(guī)則方法詞典和規(guī)則提供候選詞性消歧規(guī)

25、則進行消歧統(tǒng)計方法選擇最可能的詞性訓練用語料庫（已標注詞性）基于轉換學習的方法統(tǒng)計學習得到規(guī)則用規(guī)則方法進行詞性標注,漢語分詞（切分）,詞是語言中最小的能獨立運用的單位，也是語言信息處理的基本單位。分詞是指根據某個分詞規(guī)范，把一個“字”串劃分成“詞”串。難以確定何謂漢語的“詞”單字詞與語素的界定：豬肉、牛肉詞與短語（詞組）的界定：黑板、黑布信息處理用現代漢語分詞規(guī)范：GB-13715（1992）具體應用系統(tǒng)可根據

26、各自的需求制定規(guī)范分詞帶來的問題丟失信息、錯誤的分詞、不同的分詞規(guī)范,切分歧義及歧義字段的種類,交集型歧義字段ABC切分成AB/C或A/BC如：“和平等”“獨立/自主/和/平等/獨立/的/原則”“討論/戰(zhàn)爭/與/和平/等/問題”組合型歧義字段AB切分成AB或A/B如：“馬上”“他/騎/在/馬/上”“馬上/過來”混合型歧義由交集型歧義和組合型歧義嵌套與交叉而成如：“得到達”（交集型、組合型）“我/今晚/得/到

27、達/南京” “我/得到/達克寧/了 ” “我/得/到/達克寧/公司/去”,南京市長江大橋...,南京市長江二橋...,偽歧義與真歧義偽歧義字段指在任何情況下只有一種切分“挨批評”只有一種切分根據歧義字段本身就能消歧真歧義字段指在不同的情況下有多種切分“從小學”可以有多種切分：“從小/學” ，如：“從小/學/電腦” （“從小”是切分成“從小”還是“從/小”要根據分詞規(guī)范?。皬?小學”，如：“他/從/小學/畢業(yè)/后”根

28、據歧義字段的上下文來消歧,分詞方法,一般通過分詞詞典和分詞規(guī)則庫進行分詞。主要方法有：正向最大匹配(FMM)或逆向最大匹配(RMM)從左至右(FMM)或從右至左(RMM)，取最長的詞“幼兒園 地 節(jié)目”或“幼兒 園地 節(jié)目”雙向最大匹配分別采用FMM和RMM進行分詞如果結果一致，則認為成功；否則，采用消歧規(guī)則進行消歧（交集型歧義）：正向最大、逆向最小匹配發(fā)現組合型歧義逐詞遍歷匹配在全句中取最長的詞，去掉之，對剩下字

29、符串重復該過程 設立切分標記收集詞首字和詞尾字，把句子分成較小單位，再用某些方法切分 全切分獲得所有可能的切分，選擇最大可能的切分,基于規(guī)則的歧義字段消歧方法,利用歧義字串、前驅字串和后繼字串的句法、語義和語用信息：句法信息“陣風”：根據前面是否有數詞來消歧?！耙?陣/風/吹/過/來”、“今天/有/陣風”語義信息“了解”：“他/學會/了/解/數學/難題”（“難題”一般是“解”而不是“了解”，另外，還有“學會”)語用信息

30、“拍賣”：“乒乓球拍賣完了”，要根據場景（上下文）來確定規(guī)則的粒度基于具體的詞（個性規(guī)則）基于詞類、詞義（共性規(guī)則）Proj. 2 實現一個基于詞典與規(guī)則的漢語自動分詞系統(tǒng)。(詞典：http://nlp.nju.edu.cn/MT_Lecture/dic_ce.rar),句法分析（Parsing）,確定句子的組成（短語、短語或者詞之間的關系）。句法分析任務的類型組塊分析（淺層句法分析、部分句法分析）：基本短語（非遞歸

31、的核心成分）識別組成分分析（結構分析，完全句法分析）短語如何構成句子依存分析詞之間的依賴關系,"John ate the cat"的組成分分析,,,,,,,,,,,,S,NP,VP,NAME,John,V,NP,ate,ART,N,the,cat,"John ate the cat"的依存分析,John ate the cat,,,,sub,obj,mod,句法分析--組成分分析,句法分析

32、的目的判斷句子的合法性（句子識別）確定句子的結構（句子中單詞相互關聯的方式）基于上下文無關語法（CFG）的表示CFG能描述大部分的自然語言結構可以構造高效的基于CFG的句法分析器通常采用樹形結構來表示句法分析的結果,優(yōu)秀語法的特征,通用性能正確分析的句子的范圍選擇性能判斷出錯誤句子的范圍可理解性自身的簡易程度*魯棒性對不合法句子的容忍度（通用性）：He love her.通用性與選擇性矛盾的處置，如：忽略主謂

33、一致性檢查將導致無法區(qū)分下面句子的不同含義（歧義）Flying planes are dangerous.Flying planes is dangerous.,一個簡單的基于CFG的英語文法,1. S -> NP VP2. VP -> V NP3. NP -> NAME4. NP -> ART N5. NAME -> John6. V -> ate7. ART ->

34、; the8. N -> cat9. ......產生式5～9屬于詞法規(guī)則，一般由詞典、詞形還原以及詞性標注算法來描述 。產生式1～4屬于句法規(guī)則。,基于CFG的分析器,自頂向下利用產生式，從S開始，嘗試將S改寫/推導成與輸入句子相匹配的終結符號序列。自底向上利用產生式，嘗試將輸入句子與產生式右部進行匹配，最后規(guī)約到S?；厮菰诟膶懟蛞?guī)約的某一步可能有多個選擇。從一個錯誤的嘗試（改寫或規(guī)約）返回，進行下一個嘗

35、試。保留改寫或規(guī)約的歷史回溯需要輸出正確的分析結果也需要,一個簡單的自頂向下句法分析算法,語法1. S -> NP VP 2. NP -> ART N 3. NP -> ART ADJ N4. VP -> V 5. VP -> V NP位置計數器1 The 2 dogs 3 cried 4狀態(tài)由符號表和當前位置構成，如：((NP VP)

36、1) 表示從位置1開始尋找NP，且NP后面是VP。初始狀態(tài)為： ((S) 1)分為當前狀態(tài)和后備狀態(tài)。狀態(tài)轉換當前狀態(tài)的符號表的第一個符號是詞法符號（詞性），并且句子中當前詞屬于該詞法類，則刪除符號表中第一個符號，并更新當前位置(加1)，得到新的當前狀態(tài)。當前狀態(tài)的符號表的第一個符號是句法符號，則依據語法獲得所有以該符號為左部的產生式，用它們的右部替換符號表中的該符號，從而得到一批新的狀態(tài)，選擇其中一個作為新的當前狀態(tài)，其它作為

37、后備狀態(tài)?；厮輳暮髠錉顟B(tài)中取一個作為當前狀態(tài)，繼續(xù)分析,算法1. 取 ((S) 1)作為當前狀態(tài)（初始狀態(tài)），后備狀態(tài)為空。2. 若當前狀態(tài)為空，則失敗，算法結束，3. 否則，若當前狀態(tài)的符號表為空，(1)位置計數器值處于句子末尾，則成功，算法結束(2)位置計數器值處于句子中間，轉54. 否則，進行狀態(tài)轉換，若轉換成功，則轉25. 否則，回溯，轉2。,,“1 The 2 cat 3 caught 4 a 5 mou

38、se 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,

39、搜索策略,深度優(yōu)先后備狀態(tài)采用“棧”結構后備狀態(tài)少，存儲效率高面臨“左遞歸”問題廣度優(yōu)先后備狀態(tài)采用“隊列”結構后備狀態(tài)多，存儲效率不高,自底向上句法分析,簡單的自底向上句法分析效率不高，常常會重復嘗試相同的匹配操作（回溯之前已匹配過）。一種基于圖的句法分析技術（Chart Parsing）被提出，它把已經匹配過的結果保存起來，今后需要時可直接使用它們，不必重新匹配。（動態(tài)規(guī)劃）,Chart Parsing的數據表示,圖（

40、chart）的結點表示句子中詞之間的位置數字非活動邊集（chart的核心，常直接就被稱為chart）記錄分析中規(guī)約成功所得到的所有詞法/句法符號活動邊集未完全匹配的產生式，用加小圓圈標記（º）的產生式來表示，如：NP -> ART ºADJ NNP -> ART ºN待處理表（agenda）記錄等待加入chart的已匹配成功的詞法/句法符號上面的活動邊、非活動邊以及詞法/句法符

41、號都帶有“始/終結點”位置信息,“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

42、 5. VP->V NP,,,,N(2,3),agenda,5,6,a,mouse,重復下面的操作，直到agenda為空并且輸入中沒有下一個詞若agenda為空，則把句子中下一個詞的各種詞法符號（詞性）和它們的位置加入進來，從agenda中取一個元素（設為C，位置為：p1-p2)對下面形式的每個規(guī)則增加活動邊：X->CX1...Xn，增加一條活動邊：X->C º X1...Xn，位置為：p1-p2；

43、X->C，把X加入agenda，位置為：p1-p2將C作為非活動邊加入到chart的位置p1-p2對已有活動邊進行邊擴展對每個形式為：X->X1... º C...Xn的活動邊，若它在p0-p1之間，則增加一條活動邊：X->X1... C º...Xn，位置:p0-p2對每個形式為： X->X1... Xn º C的活動邊，若它在p0-p1之間，則把X加入agenda ，位置

44、為：p0-p2,Chart Parsing句法分析算法,“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

45、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

46、. NP->ART N 3. NP->ART ADJ N 4. VP->V 5. VP->V NP,,,,N(2,3),agenda,5,6,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 ->

47、 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”的分析過程(算法),

48、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,V(3,4),,,S -> N

49、P º 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 º ADJ N,活動邊,非活動邊,1. S->NP VP 2. NP->

50、;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,,,

51、,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,,,S -> NP º VP,,,,NP

52、,,,,,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

53、 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,,ART(4,5),,,S,,,,,NP -> ART º N,,,NP -> ART º ADJ N,,,,ART,,“1

54、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,,,

55、,agenda,5,6,a,mouse,,,,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”的分析過程(算法

56、),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,,,S -> NP

57、86; 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,

58、,,,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,,,S -> NP º VP,,,,

59、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,,,,Th

60、e,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,,,S -> NP º VP,,,,NP,,,

61、,,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 實現一個基于簡單英語語法的chart句法分析器。agenda采用棧or隊列？可能會有無用（不可能用到）的活動邊，

62、影響效率。,句法分析與邏輯程序設計,邏輯程序設計是把程序組織成一組事實（謂詞）和一組推理規(guī)則，計算（推理）過程由實現系統(tǒng)自動給出，它基于謂詞演算（Predicate Calculus）進行計算。PROLOG是一個邏輯程序設計語言，在程序中，用子句（clause）描述事實和推理規(guī)則，推理過程由PROLOG的執(zhí)行機制自動完成。對句法分析而言，事實：句子中每個詞的詞性以及詞在句子中的位置等推理規(guī)則：文法（產生式）,一個基于CFG的PR

63、OLOG句法分析器,詞典、詞形還原以及詞性標注結果可表示成事實：isart(the)isname(john)isverb(ate)isnoun(cat)......輸入句子“John ate the cat”可表示成事實：word(john,1,2)word(ate,2,3)word(the,3,4)word(cat,4,5),,語法規(guī)則可表示成推理規(guī)則：s(P1,P3):-np(P1,P2),vp(P2,P3)

64、np(P1,P3):-art(P1,P2),n(P2,P3)np(P1,P3):-name(P1,P3)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,

65、P2),isart(W)v(P1,P2):-word(W,P1,P2),isverb(W)name(P1,P2):-word(W,P1,P2),isname(W),通過查詢謂詞s(1,5)的真假來識別句子“John ate the cat”：?- s(1,5)標準PROLOG的處理策略與深度優(yōu)先的自頂向下分析方法一致。,傳統(tǒng)CFG在描述自然語言時存在的問題,1. S -> NP VP 4.

66、VP -> V2. NP -> ART N 5. VP -> V NP3. NP -> ART ADJ N上面的CFG描述了英語的一個子集，同時，它又會生成一些不合法的英語句子，如：The student solve the problem.（主謂不一致）The teacher disappeared the problem.（不及物動詞）,一種可能的解決方案－－增加句

67、法符號和規(guī)則,把NP分為NP-S和NP-P；把VP分成VP-S和VP-P：S->NP-S VP-SS->NP-P VP-P把N分成N-S和N-P：NP-S->ART N-SNP-S->ART ADJ N-SNP-P->ART N-PNP-P->ART ADJ N-P把V分成V-S-I、V-S-T、V-P-I和V-P-T：VP-S->V-S-IVP-S->V-S-T NP

68、-S VP-S->V-S-T NP-PVP-P->V-P-IVP-P->V-P-T NP-SVP-P->V-P-T NP-P,增加句法符號和規(guī)則帶來的問題,增加了規(guī)則的數量和潛在的冗余類似的規(guī)則缺乏關聯性對語言結構描述缺乏深度（表層）,基于特征的擴展CFG,不增加原CFG中的句法符號給每個句法符號增加特征（屬性），例如：NP(PER 3,NUM s) //第三人稱單數VP(PER 3,NUM

69、p) //第三人稱復數特征由特征名和特征值構成。一系列特征構成了一個特征結構（復雜特征集）。特征值可以是普通值（原子），也可以是另一個特征結構，例如：NP(AGR（PER 3, NUM s))，可簡寫為：NP(AGR 3s)一個特征的特征值可以有多個，表示成：N(ROOT fish, AGR {3s,3p}),特征值也可以是變量，表示取值可以任意，例如：NP(AGR ?a) 表示NP的AGR特征值可取任意值可以對變量形

70、式的特征值限定范圍（受限變量），例如：NP(AGR ?a{3s,3p})同名的變量表示它們的值要相同，例如：S->NP(AGR ?a) VP(AGR ?a) 表示NP與VP的AGR特征值要一致（取同樣的值，主謂一致）一個規(guī)則如果包含特征值為變量的成分，則該規(guī)則代表了一組規(guī)則（規(guī)則模板）。例如，上述規(guī)則代表：S->NP(AGR 3s) VP(AGR 3s)S->NP(AGR 3p) VP(AGR 3p)..

71、....,一個基于特征結構的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 ?a,VAL tr) NP,合一文法,一個文法可以表示成一系列特征結構間的約束關系所組成的集合。

72、這樣的文法稱為合一文法（Unification Grammar）。例如：特征結構X0、X1和X2之間的約束關系：X0->X1 X2 (CAT0=S,CAT1=NP,CAT2=VP, AGR0=AGR1=AGR2,VFORM0=VFORM2)它描述了基于特征的CFG中的一條規(guī)則：S->NP(AGR ?a) VP(AGR ?a)合一文法為基于特征的CFG文法提供了一個形式描