機器翻譯理論和技術(shù)-南京大學(xué)計算機科學(xué)與技術(shù)系

1、自然語言處理Natural Language Processing(NLP),陳家駿，戴新宇chenjj@nlp.nju.edu.cndxy@nlp.nju.edu.cn,主要內(nèi)容（1）,自然語言處理概述什么是自然語言處理自然語言處理的典型應(yīng)用自然語言處理的基本任務(wù)自然語言處理的基本策略和實現(xiàn)方法自然語言處理的難點自然語言處理所涉及的學(xué)科 (http://cs.nju.edu.cn/chenjiajun/nlp_t

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

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

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

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

6、tural Language Processing，簡稱NLP）是指用計算機對自然語言信息進行處理的方法和技術(shù)。與NLP相近的兩個研究領(lǐng)域：自然語言理解(Natural Language Understanding, NLU)：強調(diào)對語言含義和意圖的深層次解釋計算語言學(xué)(Computational Linguistics, CL)：強調(diào)可計算的語言理論,NLP技術(shù)的典型應(yīng)用,機器翻譯自動摘要文本分類與信息過濾信息檢索自動問

7、答信息抽取與文本挖掘情感分析......,機器翻譯（Machine Translation）,機器翻譯（Machine Translation，簡稱MT）是指利用計算機實現(xiàn)自然語言之間的自動翻譯。是最早的計算機應(yīng)用之一分為：文本機器翻譯和語音機器翻譯機器輔助翻譯（Machine Aided Translation或Computer Aided Translation，簡稱MAT或CAT）翻譯記憶體（Translation

8、Memory，簡稱TM）雙語對照的文本編輯...,自動摘要（Text Summarization）,利用計算機自動地從原始文檔中提取全面、準(zhǔn)確地反映該文檔中心內(nèi)容的簡潔、連貫的短文。應(yīng)對信息過載分為單文檔摘要和多文檔摘要,文本分類（Text Classification）,將一篇文檔歸于預(yù)先給定的一個類別集合中的某一類或某幾類。圖書館的圖書分類信息過濾......,信息檢索（Information Retrieval，IR

9、）,基于關(guān)鍵詞，從某文檔集合中檢索出相關(guān)的文檔。google、百度、... 主題相關(guān)的文本獲取。,自動問答（Question Answering，QA）,針對用戶提出的問題，給出具體的答案。Apple的Siri、IBM的Watson機器人、百度的“知道”、…提高信息獲取的效率,信息抽?。↖nformation Extraction，IE）,基于某個主題模板，從非結(jié)構(gòu)化或半結(jié)構(gòu)化的自然語言文本中提取出相關(guān)的結(jié)構(gòu)化信息。主題相關(guān)的

10、信息獲取。對機器翻譯、自動問答、數(shù)據(jù)挖掘（文本挖掘）等提供支持。,新華社北京３月８日電（記者李術(shù)峰）: 中國農(nóng)工民主黨第十二屆中央常務(wù)委員會第一次會議今天在北京召開。會議研究通過了貫徹落實“兩會”精神的有關(guān)決定，審議通過了中國農(nóng)工民主黨中央１９９８年工作要點（草案），并任命了中央副秘書長。農(nóng)工民主黨中央主席蔣正華主持了會議，他說，農(nóng)工民主黨有１００多名黨員作為代表和委員參加了今年的“兩會”，各位黨員要認(rèn)真履行代表和委員的職責(zé)，開好

11、會，在１９９８年的工作中認(rèn)真貫徹“兩會”精神，加強農(nóng)工民主黨的自身建設(shè)，推動事業(yè)進一步發(fā)展，為建設(shè)有中國特色社會主義事業(yè)作出新的貢獻。會前，農(nóng)工民主黨中央邀請參加“兩會”的來自全國各省、自治區(qū)、直轄市的農(nóng)工民主黨黨員進行了聯(lián)誼活動。,信息抽取實例:會議報道(人民日報1998-03-09),信息抽取的結(jié)果,情感分析（Sentiment Analysis或 Opinion Analysis ）,分析文章（評論）對某個對象（社會熱點事件、產(chǎn)

12、品或者服務(wù)）的態(tài)度（正面還是負(fù)面）。政府輿情分析：熱點事件發(fā)現(xiàn)、預(yù)警企業(yè)市場決策：產(chǎn)品意見調(diào)查、產(chǎn)品推薦消費者購買決策......,,......只要處理對象涉及自然語言的都需要NLP！,自然語言處理的基本任務(wù),語言分析：分析語言表達的結(jié)構(gòu)和含義詞法分析：形態(tài)還原、詞性標(biāo)注、命名實體（人名、地名、機構(gòu)名）識別、分詞（漢語、日語等）等句法分析：組塊分析、結(jié)構(gòu)分析、依存分析語義分析：詞義、句義（邏輯、格關(guān)系、......）

13、、篇章（上下文）（指代、實體關(guān)系、......）語言生成：從某種內(nèi)部表示生成語言表達詞、句子、篇章的生成多語言處理（機器翻譯、跨語言檢索）：語言之間的對應(yīng)、轉(zhuǎn)換不同的應(yīng)用對上述任務(wù)有不同的要求。,自然語言處理的實現(xiàn)方法,基于規(guī)則的理性方法（Rationalist approach）基于以規(guī)則形式表達的語言知識（詞、句法、語義以及轉(zhuǎn)換、生成）進行符號推理，從而實現(xiàn)信息處理。強調(diào)人對語言知識的理性整理。受Chomsky主張的人

14、具有先天語言能力觀點的影響，主宰1960－1985基于語料庫的經(jīng)驗方法（Empiricist approach）以大規(guī)模語料庫（單語和雙語）為語言知識基礎(chǔ)。利用統(tǒng)計學(xué)習(xí)和基于神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)方法自動獲取隱含在語料庫中的知識，學(xué)習(xí)到的知識體現(xiàn)為一系列模型參數(shù)。基于學(xué)習(xí)到的參數(shù)和相應(yīng)的模型進行語言信息處理。,混合方法理性方法的優(yōu)、缺點相應(yīng)的語言學(xué)理論基礎(chǔ)好語言知識描述精確處理效率高知識獲取困難（高級勞動）系統(tǒng)魯棒性差：

15、不完備的規(guī)則系統(tǒng)將導(dǎo)致推理的失敗知識擴充困難，很難保證規(guī)則之間的一致性經(jīng)驗方法的優(yōu)、缺點知識獲取容易（低級勞動）系統(tǒng)魯棒性好：概率大的作為結(jié)果知識擴充容易、一致性容易維護相應(yīng)的語言學(xué)理論基礎(chǔ)差缺乏對語言學(xué)知識的深入描述和利用，過于機械處理效率低利用各家之長，相互融合?,自然語言的分類（基于形態(tài)結(jié)構(gòu)）,分析型語言沒有或很少有詞形變化沒有表示詞的語法功能的附加成分，由詞序和虛詞表示詞之間的語法關(guān)系如：漢語黏著型語言

16、有詞形變化詞的語法意義（功能）由附加成分表達如：日語屈折型語言有詞形變化詞的語法意義由詞的形態(tài)變化來表示如：英語另外，還可以按SVO型（主－動－賓）、VSO型（動－主－賓）和SOV 型(主－賓－動) 分類,自然語言處理的難點,歧義處理有限的詞匯和規(guī)則表達復(fù)雜、多樣的對象語言知識的表示、獲取和運用成語和慣用型的處理對語言的靈活性和動態(tài)性的處理靈活性：同一個意圖的不同表達，甚至包含錯誤的語法等動態(tài)性：語言在不斷的

17、變化，如：新詞等上下文和常識知識（與語言無關(guān)）的利用和處理,漢語處理的難點,缺乏計算語言學(xué)的句法/語義理論，大都借用基于西方語言的句法/語義理論詞法分析分詞詞性標(biāo)注難句法分析主動詞識別難（特別對于流水句）詞法分類與句法功能對應(yīng)差（例如：他喜歡走）語義分析句法結(jié)構(gòu)與句義對應(yīng)差（例如：老頭曬太陽）時體態(tài)確定難 （漢語無形態(tài)變化）資源（語料庫）缺乏,自然語言處理所涉及的學(xué)科,語言學(xué)：各種語法、語義理論計算機科學(xué)（包括人

18、工智能、機器學(xué)習(xí)）數(shù)學(xué)：邏輯、概率與統(tǒng)計、信息論等哲學(xué)（認(rèn)知學(xué)）心理學(xué)......,,基于規(guī)則的自然語言處理方法 （理性方法，傳統(tǒng)方法）,概述,強調(diào)對語言知識的理性整理（知識工程）受計算語言學(xué)理論指導(dǎo)基于規(guī)則的知識表示和推導(dǎo)（符號計算）語言處理規(guī)則（數(shù)據(jù)）與程序分離，程序體現(xiàn)為規(guī)則語言的解釋器！,詞法分析,形態(tài)還原（針對英語、德語、法語等）把句子中的詞還原成它們的基本詞形。詞性標(biāo)注為句子中的詞標(biāo)上預(yù)定義類別集合

19、（標(biāo)注集）中的類。命名實體識別人名地名機構(gòu)名分詞（針對漢語、日語等）識別出句子中的詞。,形態(tài)還原（英語）,把句子中的詞還原成原形，作為詞的其它信息（詞典、個性規(guī)則）的索引。構(gòu)詞特點屈折變化：詞尾和詞形變化，詞性不變。如：study, studied,studied,studyingspeak,spoke,spoken,speaking派生變化：加前綴和后綴，詞性發(fā)生變化。如：friend,friendly,fri

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

21、?ing -> *? (VING)*ed -> * (PAST)(VEN)*ed -> *e (PAST)(VEN)*ied -> *y (PAST)(VEN)*??ed -> *? (PAST)(VEN),英語不規(guī)則動詞還原went -> go (PAST)gone -> go (VEN)sat -> sit (PAST) (VEN),形態(tài)還原算法,輸入一個單詞如果詞典里

22、有該詞，輸出該詞及其屬性，轉(zhuǎn)4，否則，轉(zhuǎn)3如果有該詞的還原規(guī)則，并且，詞典里有還原后的詞，則輸出還原后的詞及其屬性，轉(zhuǎn)4，否則，調(diào)用如果輸入中還有單詞，轉(zhuǎn)(1)，否則，結(jié)束。Proj. 1 實現(xiàn)一個英語單詞還原工具。（詞典：http://nlp.nju.edu.cn/MT_Lecture/dic_ec.rar）,詞性標(biāo)注,為句子中的詞標(biāo)上預(yù)定義類別集合（標(biāo)注集）中的類（詞性），為后續(xù)的句法/語義分析提供必要的信息。標(biāo)注體系的

23、確定標(biāo)注方法,詞性標(biāo)注體系,詞的分類按形態(tài)和句法功能（句法相關(guān)性）按表達的意思（語義相關(guān)性）兼顧上述二者,英語詞的分類,開放類（open class）Nouns句法上：可作物主、可有限定詞、有復(fù)數(shù)形式語義上：人名、地名和物名Verbs句法上：作謂語、有幾種詞形變化語義上：動作、過程（一系列動作）Adjectives句法上：修飾Nouns等語義上：性質(zhì)Adverbs句法上：修飾Verbs等語義上：方向、程度

24、、方式、時間,封閉類（closed class，function words）DeterminersPronounsPrepositionsConjunctionsAuxiliary verbsParticles（if、not、...）Numerals,,為什么要分類？分類帶來的問題？兼類詞一個詞具有兩個或者兩個以上的詞性英文的Brown語料庫中，10.4%的詞是兼類詞。例如：The back doorOn my

25、 backPromise to back the bill漢語兼類詞，例如：把門鎖上， 買了一把鎖他研究...， 研究工作漢語詞的兼類更多？與所采用的分類體系是否有關(guān)？,詞性標(biāo)注方法,規(guī)則方法詞典和規(guī)則提供候選詞性消歧規(guī)則進行消歧統(tǒng)計方法選擇最可能的詞性訓(xùn)練用語料庫（已標(biāo)注詞性）基于轉(zhuǎn)換學(xué)習(xí)的方法統(tǒng)計學(xué)習(xí)得到規(guī)則用規(guī)則方法進行詞性標(biāo)注,漢語分詞（切分）,詞是語言中最小的能獨立運用的單位，也是語言信息處理的

26、基本單位。分詞是指根據(jù)某個分詞規(guī)范，把一個“字”串劃分成“詞”串。問題：難以確定何謂漢語的“詞”單字詞與語素的界定：豬肉、牛肉詞與短語（詞組）的界定：黑板、黑布信息處理用現(xiàn)代漢語分詞規(guī)范：GB-13715（1992）具體應(yīng)用系統(tǒng)可根據(jù)各自的需求制定規(guī)范分詞帶來的問題丟失信息、錯誤的分詞、不同的分詞規(guī)范,切分歧義及歧義字段的種類,交集型歧義字段ABC切分成AB/C或A/BC如：“和平等”“獨立/自主/和/平等/獨立/

27、的/原則”“討論/戰(zhàn)爭/與/和平/等/問題”組合型歧義字段AB切分成AB或A/B如：“馬上”“他/騎/在/馬/上”“馬上/過來”混合型歧義由交集型歧義和組合型歧義嵌套與交叉而成如：“得到達”（交集型、組合型）“我/今晚/得/到達/南京” “我/得到/達克寧/了 ” “我/得/到/達克寧/公司/去”,南京市長江大橋...,南京市長江二橋...,偽歧義與真歧義偽歧義字段指在任何情況下只有一種切分“挨批評”只有一種

28、切分根據(jù)歧義字段本身就能消歧真歧義字段指在不同的情況下有多種切分“從小學(xué)”可以有多種切分：“從小/學(xué)” ，如：“從小/學(xué)/電腦” （“從小”是切分成“從小”還是“從/小”要根據(jù)分詞規(guī)范?。皬?小學(xué)”，如：“他/從/小學(xué)/畢業(yè)/后”根據(jù)歧義字段的上下文來消歧,分詞方法,一般通過分詞詞典和分詞規(guī)則庫進行分詞。主要方法有：正向最大匹配(FMM)或逆向最大匹配(RMM)從左至右(FMM)或從右至左(RMM)，取最長的詞“幼兒

29、園 地 節(jié)目”或“幼兒 園地 節(jié)目”雙向最大匹配分別采用FMM和RMM進行分詞如果結(jié)果一致，則認(rèn)為成功；否則，采用消歧規(guī)則進行消歧（交集型歧義）：正向最大、逆向最小匹配發(fā)現(xiàn)組合型歧義逐詞遍歷匹配在全句中取最長的詞，去掉之，對剩下字符串重復(fù)該過程 設(shè)立切分標(biāo)記收集詞首字和詞尾字，把句子分成較小單位，再用某些方法切分 全切分獲得所有可能的切分，選擇最大可能的切分,基于規(guī)則的歧義字段消歧方法,利用歧義字串、前驅(qū)字串和后

30、繼字串的句法、語義和語用信息：句法信息“陣風(fēng)”：根據(jù)前面是否有數(shù)詞來消歧?！耙?陣/風(fēng)/吹/過/來”、“今天/有/陣風(fēng)”語義信息“了解”：“他/學(xué)會/了/解/數(shù)學(xué)/難題”（“難題”一般是“解”而不是“了解”，另外，還有“學(xué)會”)語用信息“拍賣”：“乒乓球拍賣完了”，要根據(jù)場景（上下文）來確定規(guī)則的粒度基于具體的詞（個性規(guī)則）基于詞類、詞義（共性規(guī)則）Proj. 2 實現(xiàn)一個基于詞典與規(guī)則的漢語自動分詞系統(tǒng)。(詞典

31、：http://nlp.nju.edu.cn/MT_Lecture/dic_ce.rar),句法分析（Parsing）,確定句子的組成詞、短語以及它們之間的關(guān)系句法分析任務(wù)的類型組塊分析（淺層句法分析、部分句法分析）：基本短語（非遞歸的核心成分）識別組成分分析（結(jié)構(gòu)分析，完全句法分析）短語如何構(gòu)成句子依存分析詞之間的依賴關(guān)系,"John ate the cat"的組成分分析,,,,,,,,,,,,S,

32、NP,VP,NAME,John,V,NP,ate,ART,N,the,cat,"John ate the cat"的依存分析,John ate the cat,,,,sub,obj,mod,句法分析--組成分分析,句法分析的目的判斷句子的合法性（句子識別）確定句子的結(jié)構(gòu)（句子中單詞相互關(guān)聯(lián)的方式）基于上下文無關(guān)語法（CFG）的表示CFG能描述大部分的自然語言結(jié)構(gòu)可以構(gòu)造高效的基于CFG的句法分析器通常采用

33、樹形結(jié)構(gòu)來表示句法分析的結(jié)果,優(yōu)秀語法的特征,通用性能正確分析的句子的范圍選擇性能判斷出錯誤句子的范圍可理解性自身的簡易程度*魯棒性對不合法句子的容忍度（通用性）：He love her.通用性與選擇性矛盾的處置，如：忽略主謂一致性檢查將導(dǎo)致無法區(qū)分下面句子的不同含義（歧義）Flying planes are dangerous.Flying planes is dangerous.,一個簡單的基于CFG的英語文法,

34、1. S -> NP VP2. VP -> V NP3. NP -> NAME4. NP -> ART N5. NAME -> John6. V -> ate7. ART -> the8. N -> cat9. ......產(chǎn)生式5～9屬于詞法規(guī)則，一般由詞典、詞形還原以及詞性標(biāo)注算法來描述 。產(chǎn)生式1～4屬于句法規(guī)則。,基于CFG的分析器,自頂向下

35、利用產(chǎn)生式，從S開始，嘗試將S改寫/推導(dǎo)成與輸入句子相匹配的終結(jié)符號序列。自底向上利用產(chǎn)生式，嘗試將輸入句子與產(chǎn)生式右部進行匹配，最后規(guī)約到S?；厮菰诟膶懟蛞?guī)約的某一步可能有多個選擇。從一個錯誤的嘗試（改寫或規(guī)約）返回，進行下一個嘗試。保留改寫或規(guī)約的歷史回溯需要輸出正確的分析結(jié)果也需要,一個簡單的自頂向下句法分析算法,語法1. S -> NP VP 2. NP -> ART N

36、 3. NP -> ART ADJ N4. VP -> V 5. VP -> V NP位置計數(shù)器1 The 2 dogs 3 cried 4狀態(tài)由符號表和當(dāng)前位置構(gòu)成，如：((NP VP) 1) 表示從位置1開始尋找NP，且NP后面是VP。初始狀態(tài)為： ((S) 1)分為當(dāng)前狀態(tài)和后備狀態(tài)。狀態(tài)轉(zhuǎn)換當(dāng)前狀態(tài)的符號表的第一個符號是詞法符號（詞性），并且句子中當(dāng)前詞屬于該詞法類，則刪

37、除符號表中第一個符號，并更新當(dāng)前位置(加1)，得到新的當(dāng)前狀態(tài)。當(dāng)前狀態(tài)的符號表的第一個符號是句法符號，則依據(jù)語法獲得所有以該符號為左部的產(chǎn)生式，用它們的右部替換符號表中的該符號，從而得到一批新的狀態(tài)，選擇其中一個作為新的當(dāng)前狀態(tài)，其它作為后備狀態(tài)?；厮輳暮髠錉顟B(tài)中取一個作為當(dāng)前狀態(tài)，繼續(xù)分析,算法1. 取 ((S) 1)作為當(dāng)前狀態(tài)（初始狀態(tài)），后備狀態(tài)為空。2. 若當(dāng)前狀態(tài)為空，則失敗，算法結(jié)束，3. 否則，若當(dāng)前狀態(tài)的

38、符號表為空，(1)位置計數(shù)器值處于句子末尾，則成功，算法結(jié)束(2)位置計數(shù)器值處于句子中間，轉(zhuǎn)54. 否則，進行狀態(tài)轉(zhuǎn)換，若轉(zhuǎn)換成功，則轉(zhuǎn)25. 否則，回溯，轉(zhuǎn)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

39、 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)采用“棧”結(jié)構(gòu)后備狀態(tài)少，存儲效率高面臨“左遞歸”問題廣度優(yōu)先后備狀態(tài)采用“隊列”結(jié)構(gòu)后備狀態(tài)多，存儲效率不高,自底向上句法分析,簡單的自底向上句法分析效率不高

40、，常常會重復(fù)嘗試相同的匹配操作（回溯之前已匹配過）。一種基于圖的句法分析技術(shù)（Chart Parsing）被提出，它把已經(jīng)匹配過的結(jié)果保存起來，今后需要時可直接使用它們，不必重新匹配。（動態(tài)規(guī)劃）,Chart Parsing的數(shù)據(jù)表示,圖（chart）的結(jié)點表示句子中詞之間的位置數(shù)字非活動邊集（chart的核心，常直接就被稱為chart）記錄分析中規(guī)約成功所得到的所有詞法/句法符號活動邊集未完全匹配的產(chǎn)生式，用加小圓圈標(biāo)記（&

41、#186;）的產(chǎn)生式來表示，如：NP -> ART ºADJ NNP -> ART ºN待處理表（agenda）記錄等待加入chart的已匹配成功的詞法/句法符號上面的活動邊、非活動邊以及詞法/句法符號都帶有“始/終結(jié)點”位置信息,“1 The 2 cat 3 caught 4 a 5 mouse 6”分析中的數(shù)據(jù)示例,1,2,3,4,,,,The,cat,caught,ART,,,,NP -&

42、gt; 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,a,mouse,重復(fù)下面的操作，直到agenda為空并且輸入中沒有下一個詞若agenda為空，則把句子中下一個詞的各種詞法

43、符號（詞性）和它們的位置加入進來，從agenda中取一個元素（設(shè)為C，位置為：p1-p2)對下面形式的每個規(guī)則增加活動邊：X->CX1...Xn，增加一條活動邊：X->C º X1...Xn，位置為：p1-p2；X->C，把X加入agenda，位置為：p1-p2將C作為非活動邊加入到chart的位置p1-p2對已有活動邊進行邊擴展對每個形式為：X->X1... º C...Xn的

44、活動邊，若它在p0-p1之間，則增加一條活動邊：X->X1... C º...Xn，位置:p0-p2對每個形式為： X->X1... Xn º C的活動邊，若它在p0-p1之間，則把X加入agenda ，位置為：p0-p2,Chart Parsing句法分析算法,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程 (算法),1,2,3,4,,,,The,cat,caug

45、ht,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,,,,ART(1,2),agenda,5,6,a,mouse,“1 The 2 cat 3 caught 4 a 5 mouse 6”的

46、分析過程 (算法),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,a,mouse,,,,N,

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

48、->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,,,,The,cat,caught,ART,,,,NP -> ART º N,,,,NP -> ART º ADJ N,活動邊,非活動邊,1. S-&

49、gt;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”的分析過程(算

50、法),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 &#

51、186; 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

52、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,,,V,,,,VP,,S(1,4),,,S,,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過程(算法),1,2,

53、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 º VP

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

55、,,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,,,,,VP -> V º NP,,,V,,,,VP,,N(5,6),,,

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

57、->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,,,V,,,,VP,,,,S,,,,,NP -> ART º N,,,NP -> ART º

58、; 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

59、 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,,,V,,,,VP,,,,S,,,,,NP -> ART º N,,,NP -> ART º ADJ N,,,

60、,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.

61、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,,,V,,,,VP,,,,S,,,,,NP -> ART º N,,,NP -> ART º ADJ N,,,,ART,

62、,,,N,,,,S -> NP º VP,,,,NP,,,,VP,,S(1,6),,,S,,,Proj. 3 實現(xiàn)一個基于簡單英語語法的chart句法分析器。agenda采用棧or隊列？可能會有無用（不可能用到）的活動邊，影響效率。,句法分析與邏輯程序設(shè)計,邏輯程序設(shè)計是把程序組織成一組事實（謂詞）和一組推理規(guī)則，計算（推理）過程由實現(xiàn)系統(tǒng)自動給出，它基于謂詞演算（Predicate Calculus）進行計算。P

63、ROLOG是一個邏輯程序設(shè)計語言，在程序中，用子句（clause）描述事實和推理規(guī)則，推理過程由PROLOG的執(zhí)行機制自動完成。對句法分析而言，事實：句子中每個詞的詞性以及詞在句子中的位置等推理規(guī)則：文法（產(chǎn)生式）,一個基于CFG的PROLOG句法分析器,詞典、詞形還原以及詞性標(biāo)注結(jié)果可表示成事實：isart(the)isname(john)isverb(ate)isnoun(cat)......輸入句子“John a

64、te 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)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

65、,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),通過查詢謂詞s(1,5)的真假

66、來識別句子“John ate the cat”：?- s(1,5)標(biāo)準(zhǔn)PROLOG的處理策略與深度優(yōu)先的自頂向下分析方法一致。,傳統(tǒng)CFG在描述自然語言時存在的問題,1. S -> NP VP 4. VP -> V2. NP -> ART N 5. VP -> V NP3. NP -> ART ADJ N上面的CFG描述了英語的一個子集，

67、同時，它又會生成一些不合法的英語句子，如：The student solve the problem.（主謂不一致）The teacher disappeared the problem.（不及物動詞）,一種可能的解決方案－－增加句法符號和規(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-S

68、NP-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-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ī)則

69、的數(shù)量和潛在的冗余類似的規(guī)則缺乏關(guān)聯(lián)性對語言結(jié)構(gòu)描述缺乏深度（表層）,基于特征的擴展CFG,不增加原CFG中的句法符號給每個句法符號增加特征（屬性），例如：NP(PER 3,NUM s) //第三人稱單數(shù)VP(PER 3,NUM p) //第三人稱復(fù)數(shù)特征由特征名和特征值構(gòu)成。一系列特征構(gòu)成了一個特征結(jié)構(gòu)（復(fù)雜特征集）。特征值可以是普通值（原子），也可以是另一個特征結(jié)構(gòu)，例如：NP(AGR（PER 3, NUM s)

70、)，可簡寫為：NP(AGR 3s)一個特征的特征值可以有多個，表示成：N(ROOT fish, AGR {3s,3p}),特征值也可以是變量，表示取值可以任意，例如：NP(AGR ?a) 表示NP的AGR特征值可取任意值可以對變量形式的特征值限定范圍（受限變量），例如：NP(AGR ?a{3s,3p})同名的變量表示它們的值要相同，例如：S->NP(AGR ?a) VP(AGR ?a) 表示NP與VP的AGR特征值

71、要一致（取同樣的值，主謂一致）一個規(guī)則如果包含特征值為變量的成分，則該規(guī)則代表了一組規(guī)則（規(guī)則模板）。例如，上述規(guī)則代表：S->NP(AGR 3s) VP(AGR 3s)S->NP(AGR 3p) VP(AGR 3p)......,一個基于特征結(jié)構(gòu)的CFG語法,S->NP(AGR ?a) VP(AGR ?a)NP(AGR ?a) -> ART N(AGR ?a)NP(AGR ?a) -> ART

72、 ADJ N(AGR ?a)VP(AGR ?a) -> V(AGR ?a,VAL itr)VP(AGR ?a) -> V(AGR ?a,VAL tr) NP,合一文法,一個文法可以表示成一系列特征結(jié)構(gòu)間的約束關(guān)系所組成的集合。這樣的文法稱為合一文法（Unification Grammar）。例如：特征結(jié)構(gòu)X0、X1和X2之間的約束關(guān)系：X0->X1 X2 (CAT0=S,CAT1=NP,CAT2=VP,