自然語言處理

NaturalLanguageProcessing(NLP)陳家駿，戴新宇chenjj@dxy@自然語言處理NLP第1頁主要內(nèi)容（1）自然語言處理概述什么是自然語言處理自然語言處理技術應用自然語言處理基本策略和實現(xiàn)方法自然語言處理難點自然語言處理所包括學科(/chenjiajun/nlp_traditional.ppt)自然語言處理NLP第2頁基于規(guī)則自然語言處理方法（理性方法，傳統(tǒng)方法）基于詞典和規(guī)則形態(tài)還原（英語）、詞性標注以及分詞（漢語、日語）基于CFG（上下文無關文法）和擴充CFG（復雜特征集、合一運算）句法表示及其分析技術基于邏輯形式和格語法句義分析基于規(guī)則機器翻譯(/chenjiajun/nlp_traditional.ppt)主要內(nèi)容（2）自然語言處理NLP第3頁基于語料庫自然語言處理方法（經(jīng)驗方法）語言模型（N元文法）分詞、詞性標注（序列化標注模型）句法分析（概率上下文無關模型）文本分類（樸素貝葉斯模型、最大熵模型）機器翻譯(IBMModel等)......（基于神經(jīng)網(wǎng)絡深度學習方法）主要內(nèi)容（3）自然語言處理NLP第4頁所需前導知識編譯技術概率與統(tǒng)計自然語言處理NLP第5頁參考書籍宗成慶，統(tǒng)計自然語言處理，清華大學出版社，劉群等譯，自然語言了解（第二版），電子工業(yè)出版社，苑春法等譯，統(tǒng)計自然語言處理基礎，電子工業(yè)出版社，馮志偉等譯，自然語言處理綜論，電子工業(yè)出版社，黃昌寧等，語料庫語言學，商務印書館，馮志偉，計算語言學基礎，商務印書館，余士文，計算語言學概論，商務印書館，姚天順，自然語言了解－－一個讓機器知道人類語言研究（第2版），清華大學出版社，趙鐵軍等，機器翻譯原理，哈爾濱工業(yè)大學出版社，宗成慶等譯，統(tǒng)計機器翻譯，電子工業(yè)出版社，PeterF.Brown,etal.,AStatisticalApproachtoMT,ComputationalLinguistics,1990,16(2)自然語言處理NLP第6頁課程考評Projects提交匯報（說明基本做法）和源程序及可運行程序期末筆試自然語言處理NLP第7頁自然語言處理概述自然語言處理NLP第8頁什么是自然語言處理充分利用信息將會給人們帶來巨大收益，而大量信息以自然語言（英語、漢語等）形式存在。怎樣有效地獲取和利用以自然語言形式出現(xiàn)信息？自然語言處理（NaturalLanguageProcessing，簡稱NLP）是指用計算機對語言信息進行處理方法和技術。與NLP相近兩個研究領域：自然語言了解(NaturalLanguageUnderstanding,NLU)：強調(diào)對語言含義和意圖深層次解釋計算語言學(ComputationalLinguistics,CL)：強調(diào)可計算語言理論自然語言處理NLP第9頁NLP技術應用機器翻譯自動摘要文本分類與信息過濾信息檢索信息抽取與文本挖掘情感分析自動問答......自然語言處理NLP第10頁機器翻譯（MachineTranslation）機器翻譯（MachineTranslation，簡稱MT）是指利用計算機實現(xiàn)自然語言（英語、漢語等）之間自動翻譯。是最早計算機應用之一分為：文本機器翻譯和語音機器翻譯機器輔助翻譯（MachineAidedTranslation或ComputerAidedTranslation，簡稱MAT或CAT）翻譯記憶體（TranslationMemory，簡稱TM）雙語對照文本編輯...自然語言處理NLP第11頁自動摘要（TextSummarization）利用計算機自動地從原始文檔中提取全方面準確地反應該文檔中心內(nèi)容簡練、連貫短文。指標：壓縮比、...

自然語言處理NLP第12頁文本分類（TextClassification）將一篇文檔歸于預先給定一個類別集合中某一類或某幾類?？捎糜趫D書館圖書分類信息過濾......自然語言處理NLP第13頁信息檢索（InformationRetrieval，IR）主題相關文本獲取?；陉P鍵詞，從某文檔集合中檢索出相關文檔。關鍵技術：倒排索引、...谷歌、baidu、...

自然語言處理NLP第14頁信息抽?。↖nformationExtraction，IE）主題相關信息獲取?；谀硞€主題模板，從非結(jié)構(gòu)化或半結(jié)構(gòu)化自然語言文本中提取出相關結(jié)構(gòu)化信息。對機器翻譯、自動問答、數(shù)據(jù)挖掘（文本挖掘）等提供支持。自然語言處理NLP第15頁新華社北京３月８日電（記者李術峰）:中國農(nóng)工民主黨第十二屆中央常務委員會第一次會議今天在北京召開。會議研究經(jīng)過了落實落實“兩會”精神相關決定，審議經(jīng)過了中國農(nóng)工民主黨中央１９９８年工作關鍵點（草案），并任命了中央副秘書長。農(nóng)工民主黨中央主席蔣正華主持了會議，他說，農(nóng)工民主黨有１００多名黨員作為代表和委員參加了今年“兩會”，各位黨員要認真推行代表和委員職責，開好會，在１９９８年工作中認真落實“兩會”精神，加強農(nóng)工民主黨本身建設，推進事業(yè)深入發(fā)展，為建設有中國特色社會主義事業(yè)作出新貢獻。會前，農(nóng)工民主黨中央邀請參加“兩會”來自全國各省、自治區(qū)、直轄市農(nóng)工民主黨黨員進行了聯(lián)誼活動。信息抽取實例:會議報道(人民日報1998-03-09)自然語言處理NLP第16頁信息抽取結(jié)果會議時間Time

１９９８年3月8日會議地點Spot

北京會議召集者/主持人Convener個人姓名/團體名稱Name蔣正華機構(gòu)、職位Org/Post主席，農(nóng)工民主黨中央會議名/標題Conf-Title

中國農(nóng)工民主黨第十二屆中央常務委員會第一次會議

自然語言處理NLP第17頁情感分析（SentimentAnalysis或OpinionAnalysis）分析文章（評論）對某個對象（社會熱點事件、產(chǎn)品或者服務）態(tài)度（正面還是負面）。政府輿情分析：熱點事件發(fā)覺、預警企業(yè)市場決議：產(chǎn)品意見調(diào)查、產(chǎn)品推薦消費者購置決議......自然語言處理NLP第18頁自動問答（QuestionAnswering，QA）針對用戶提出問題，給出詳細答案。AppleSiri、IBMWatson機器人、baidu“知道”、…自然語言處理NLP第19頁自然語言處理主要任務（工作）語言分析：分析語言表示結(jié)構(gòu)和含義詞法分析：形態(tài)還原、詞性標注、命名實體識別、分詞（漢語、日語等）等句法分析：組塊分析、結(jié)構(gòu)分析、依存分析語義分析：詞義、句義（邏輯、格關系、...）、篇章（上下文）（指代、實體關系）語言生成：從某種內(nèi)部表示生成語言表示多語言處理（機器翻譯、跨語言檢索）：語言之間對應、轉(zhuǎn)換不一樣應用對上述任務有不一樣要求。自然語言處理NLP第20頁自然語言分類（基于形態(tài)結(jié)構(gòu)）分析型語言詞形改變極少沒有表示詞語法功效附加成份，由詞序和虛詞表示詞之間語法關系漢語、藏語等黏著型語言有詞形改變詞語法意義（功效）由附加成份表示日語、芬蘭語等屈折型語言有詞形改變詞語法意義由詞形態(tài)改變來表示英語、德語、法語等另外，還能夠按SVO型（主－動－賓）、VSO型（動－主－賓）和SOV型(主－賓－動)分類自然語言處理NLP第21頁自然語言處理實現(xiàn)方法基于規(guī)則理性方法（Rationalistapproach）基于以規(guī)則形式表示語言知識（詞、句法、語義以及轉(zhuǎn)換、生成）進行推理。強調(diào)人對語言知識理性整理。受Chomsky主張人含有先天語言能力觀點影響，主宰1960－1985基于語料庫經(jīng)驗方法（Empiricistapproach）以大規(guī)模語料庫（單語和雙語）為語言知識基礎。利用統(tǒng)計學習和基于神經(jīng)網(wǎng)絡深度學習方法自動獲取和利用隱含在語料庫中知識。學習到知識表示為一系列模型參數(shù)。自然語言處理NLP第22頁混合方法理性方法優(yōu)、缺點對應語言學理論基礎好語言知識描述準確處理效率高知識獲取困難（高級勞動）系統(tǒng)魯棒性（適應性）差：不完備規(guī)則系統(tǒng)將造成推理失敗知識擴充困難，極難確保規(guī)則之間一致性經(jīng)驗方法優(yōu)、缺點知識獲取輕易（低級勞動）系統(tǒng)魯棒性好：概率大作為結(jié)果知識擴充輕易、一致性輕易維護對應語言學理論基礎差缺乏對語言學知識深入描述和利用，過于機械處理效率低利用各家之長，相互融合自然語言處理NLP第23頁自然語言處理難點歧義處理有限詞匯和規(guī)則表示復雜、多樣對象語言知識表示、獲取和利用成語和慣用型處理對語言靈活性和動態(tài)性處理靈活性：同一個意圖不一樣表示，甚至包含錯誤語法等動態(tài)性：語言在不停改變，如：新詞等上下文和世界知識（常識，語言無關）利用和處理自然語言處理NLP第24頁漢語處理難點缺乏計算語言學句法/語義理論，大都借用基于西方語言句法/語義理論詞法分析分詞詞性標注難句法分析主動詞識別難詞法分類與句法功效對應差語義分析句法結(jié)構(gòu)與句義對應差時體態(tài)確定難（漢語無形態(tài)改變）資源（語料庫）缺乏自然語言處理NLP第25頁自然語言處理所包括學科計算語言學：各種語法、語義理論計算機科學（包含人工智能、機器學習）數(shù)學：邏輯、概率與統(tǒng)計、信息論等哲學（認知學）心理學......自然語言處理NLP第26頁基于規(guī)則自然語言處理方法（理性方法，傳統(tǒng)方法）自然語言處理NLP第27頁概述強調(diào)對語言知識理性整理（知識工程）受計算語言學理論指導基于規(guī)則知識表示和推導（符號計算）語言處理規(guī)則（數(shù)據(jù)）與程序分離，程序表達為規(guī)則語言解釋器！自然語言處理NLP第28頁詞法分析形態(tài)還原（針對英語、德語、法語等）把句子中詞還原成基本詞形。詞性標注為句子中詞標上預定義類別集合（標注集）中類。命名實體識別人名地名機構(gòu)名分詞（針對漢語、日語等）識別出句子中詞。自然語言處理NLP第29頁形態(tài)還原（英語）把句子中詞還原成原形，作為詞其它信息（詞典、個性規(guī)則）索引。構(gòu)詞特點屈折改變：詞尾和詞形改變，詞性不變。如：study,studied,studied,studyingspeak,spoke,spoken,speaking派生改變：加前綴和后綴，詞性發(fā)生改變。如：friend,friendly,friendship,...復合改變：多個單詞以某種方式組合成一個詞。還原規(guī)則通用規(guī)則：改變有規(guī)律個性規(guī)則：改變無規(guī)律自然語言處理NLP第30頁形態(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)自然語言處理NLP第31頁英語不規(guī)則動詞還原went->go(PAST)gone->go(VEN)sat->sit(PAST)(VEN)自然語言處理NLP第32頁形態(tài)還原算法輸入一個單詞假如詞典里有該詞，輸出該詞及其屬性，轉(zhuǎn)4，不然，轉(zhuǎn)3假如有該詞還原規(guī)則，而且，詞典里有還原后詞，則輸出還原后詞及其屬性，轉(zhuǎn)4，不然，調(diào)用<未登錄詞模塊>假如輸入中還有單詞，轉(zhuǎn)(1)，不然，結(jié)束。Proj.1實現(xiàn)一個英語單詞還原工具。（詞典：/MT_Lecture/dic_ec.rar）自然語言處理NLP第33頁詞性標注為句子中詞標上預定義類別集合（標注集）中類（詞性），為后續(xù)句法/語義分析提供必要信息。標注體系確實定標注方法自然語言處理NLP第34頁詞性標注體系詞分類按形態(tài)和句法功效（句法相關性）按表示意思（語義相關性）兼顧上述二者自然語言處理NLP第35頁英語詞分類開放類（openclass）Nouns句法上：可作物主、可有限定詞、有復數(shù)形式語義上：人名、地名和物名Verbs句法上：作謂語、有幾個詞形改變語義上：動作、過程（一系列動作）Adjectives句法上：修飾Nouns等語義上：性質(zhì)Adverbs句法上：修飾Verbs等語義上：方向、程度、方式、時間自然語言處理NLP第36頁封閉類（closedclass，functionwords）DeterminersPronounsPrepositionsConjunctionsAuxiliaryverbsParticles（if、not、...）Numerals自然語言處理NLP第37頁為何要分類？分類帶來問題？兼類詞一個詞含有兩個或者兩個以上詞性英文Brown語料庫中，10.4%詞是兼類詞。比如：ThebackdoorOnmybackPromisetobackthebill漢語兼類詞，比如：把門鎖上，買了一把鎖他研究...，研究工作漢語詞兼類更多？與所采取分類體系是否相關？自然語言處理NLP第38頁詞性標注方法規(guī)則方法詞典和規(guī)則提供候選詞性消歧規(guī)則進行消歧統(tǒng)計方法選擇最可能詞性訓練用語料庫（已標注詞性）基于轉(zhuǎn)換學習方法統(tǒng)計學習得到規(guī)則用規(guī)則方法進行詞性標注自然語言處理NLP第39頁漢語分詞（切分）詞是語言中最小能獨立利用單位，也是語言信息處理基本單位。分詞是指依據(jù)某個分詞規(guī)范，把一個“字”串劃分成“詞”串。難以確定何謂漢語“詞”單字詞與語素界定：豬肉、牛肉詞與短語（詞組）界定：黑板、黑布信息處理用當代漢語分詞規(guī)范：GB-13715（1992）詳細應用系統(tǒng)可依據(jù)各自需求制訂規(guī)范分詞帶來問題丟失信息、錯誤分詞、不一樣分詞規(guī)范自然語言處理NLP第40頁切分歧義及歧義字段種類交集型歧義字段ABC切分成AB/C或A/BC如：“和平等”“獨立/自主/和/平等/獨立//標準”“討論/戰(zhàn)爭/與/和平/等/問題”組合型歧義字段AB切分成AB或A/B如：“馬上”“他/騎/在/馬/上”“馬上/過來”混合型歧義由交集型歧義和組合型歧義嵌套與交叉而成如：“得抵達”（交集型、組合型）“我/今晚/得/抵達/南京”“我/得到/達克寧/了”“我/得/到/達克寧/企業(yè)/去”南京市長江大橋...南京市長江二橋...自然語言處理NLP第41頁偽歧義與真歧義偽歧義字段指在任何情況下只有一個切分“挨批評”只有一個切分依據(jù)歧義字段本身就能消歧真歧義字段指在不一樣情況下有各種切分“從小學”能夠有各種切分：“從小/學”，如：“從小/學/電腦”（“從小”是切分成“從小”還是“從/小”要依據(jù)分詞規(guī)范！）“從/小學”，如：“他/從/小學/畢業(yè)/后”依據(jù)歧義字段上下文來消歧自然語言處理NLP第42頁分詞方法

普通經(jīng)過分詞詞典和分詞規(guī)則庫進行分詞。主要方法有：正向最大匹配(FMM)或逆向最大匹配(RMM)從左至右(FMM)或從右至左(RMM)，取最長詞“幼稚園地節(jié)目”或“幼兒園地節(jié)目”雙向最大匹配分別采取FMM和RMM進行分詞假如結(jié)果一致，則認為成功；不然，采取消歧規(guī)則進行消歧（交集型歧義）：正向最大、逆向最小匹配發(fā)覺組合型歧義逐詞遍歷匹配在全句中取最長詞，去掉之，對剩下字符串重復該過程設置切分標識搜集詞首字和詞尾字，把句子分成較小單位，再用一些方法切分全切分取得全部可能切分，選擇最大可能切分自然語言處理NLP第43頁基于規(guī)則歧義字段消歧方法利用歧義字串、前驅(qū)字串和后繼字串句法、語義和語用信息：句法信息“陣風”：依據(jù)前面是否有數(shù)詞來消歧?！耙?陣/風/吹/過/來”、“今天/有/陣風”語義信息“了解”：“他/學會/了/解/數(shù)學/難題”（“難題”普通是“解”而不是“了解”，另外，還有“學會”)語用信息“拍賣”：“乒乓球拍賣完了”，要依據(jù)場景（上下文）來確定規(guī)則粒度基于詳細詞（個性規(guī)則）基于詞類、詞義（共性規(guī)則）Proj.2實現(xiàn)一個基于詞典與規(guī)則漢語自動分詞系統(tǒng)。(詞典：/MT_Lecture/dic_ce.rar)自然語言處理NLP第44頁句法分析（Parsing）確定句子組成（短語、短語或者詞之間關系）。句法分析任務類型組塊分析（淺層句法分析、部分句法分析）：基本短語（非遞歸關鍵成份）識別組成份分析（結(jié)構(gòu)分析，完全句法分析）短語怎樣組成句子依存分析詞之間依賴關系自然語言處理NLP第45頁"Johnatethecat"組成份分析SNPVPNAMEJohnVNPateARTNthecat自然語言處理NLP第46頁"Johnatethecat"依存分析Johnatethecatsubobjmod自然語言處理NLP第47頁句法分析--組成份分析句法分析目標判斷句子正當性（句子識別）確定句子結(jié)構(gòu)（句子中單詞相互關聯(lián)方式）基于上下文無關語法（CFG）表示CFG能描述大部分自然語言結(jié)構(gòu)能夠結(jié)構(gòu)高效基于CFG句法分析器通常采取樹形結(jié)構(gòu)來表示句法分析結(jié)果自然語言處理NLP第48頁優(yōu)異語法特征通用性能正確分析句子范圍選擇性能判斷犯錯誤句子范圍可了解性本身簡易程度*魯棒性對不正當句子容忍度（通用性）：Heloveher.通用性與選擇性矛盾處置，如：忽略主謂一致性檢驗將造成無法區(qū)分下面句子不一樣含義（歧義）Flyingplanesaredangerous.Flyingplanesisdangerous.自然語言處理NLP第49頁一個簡單基于CFG英語文法1.S->NPVP2.VP->VNP3.NP->NAME4.NP->ARTN5.NAME->John6.V->ate7.ART->the8.N->cat9.......產(chǎn)生式5～9屬于詞法規(guī)則，普通由詞典、詞形還原以及詞性標注算法來描述。產(chǎn)生式1～4屬于句法規(guī)則。自然語言處理NLP第50頁基于CFG分析器自頂向下利用產(chǎn)生式，從S開始，嘗試將S改寫/推導成與輸入句子相匹配終止符號序列。自底向上利用產(chǎn)生式，嘗試將輸入句子與產(chǎn)生式右部進行匹配，最終規(guī)約到S?；厮菰诟膶懟蛞?guī)約某一步可能有多個選擇。從一個錯誤嘗試（改寫或規(guī)約）返回，進行下一個嘗試。保留改寫或規(guī)約歷史回溯需要輸出正確分析結(jié)果也需要自然語言處理NLP第51頁一個簡單自頂向下句法分析算法語法1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNP位置計數(shù)器1The2dogs3cried4狀態(tài)由符號表和當前位置組成，如：((NPVP)1)表示從位置1開始尋找NP，且NP后面是VP。初始狀態(tài)為：((S)1)分為當前狀態(tài)和后備狀態(tài)。狀態(tài)轉(zhuǎn)換當前狀態(tài)符號表第一個符號是詞法符號（詞性），而且句子中當前詞屬于該詞法類，則刪除符號表中第一個符號，并更新當前位置(加1)，得到新當前狀態(tài)。當前狀態(tài)符號表第一個符號是句法符號，則依據(jù)語法取得全部以該符號為左部產(chǎn)生式，用它們右部替換符號表中該符號，從而得到一批新狀態(tài)，選擇其中一個作為新當前狀態(tài)，其它作為后備狀態(tài)。回溯從后備狀態(tài)中取一個作為當前狀態(tài)，繼續(xù)分析自然語言處理NLP第52頁算法1.取((S)1)作為當前狀態(tài)（初始狀態(tài)），后備狀態(tài)為空。2.若當前狀態(tài)為空，則失敗，算法結(jié)束，3.不然，若當前狀態(tài)符號表為空，

(1)位置計數(shù)器值處于句子末尾，則成功，算法結(jié)束

(2)位置計數(shù)器值處于句子中間，轉(zhuǎn)54.不然，進行狀態(tài)轉(zhuǎn)換，若轉(zhuǎn)換成功，則轉(zhuǎn)25.不然，回溯，轉(zhuǎn)2。自然語言處理NLP第53頁步驟當前狀態(tài)后備狀態(tài)備注1((S)1)初始狀態(tài)2((NPVP)1)規(guī)則1改寫3((ARTNVP)1)((ARTADJNVP)1)規(guī)則2、3改寫4((NVP)2)((ARTADJNVP)1)ART匹配the5((VP)3)((ARTADJNVP)1)N匹配cat6((V)3)((VNP)3)((ARTADJNVP)1)規(guī)則4、5改寫7(()4)((VNP)3)((ARTADJNVP)1)V匹配caught“1The2cat3caught4a5mouse6”分析過程1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNP自然語言處理NLP第54頁步驟當前狀態(tài)后備狀態(tài)備注8((VNP)3)((ARTADJNVP)1)回溯9((NP)4)((ARTADJNVP)1)V匹配caught10((ARTN)4)((ARTADJN)4)((ARTADJNVP)1)規(guī)則2、3改寫11((N)5)((ARTADJN)4)((ARTADJNVP)1)ART匹配a12(()6)((ARTADJN)4)((ARTADJNVP)1)N匹配mouse13結(jié)束“1The2cat3caught4a5mouse6”分析過程（續(xù)）1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNP自然語言處理NLP第55頁搜索策略深度優(yōu)先后備狀態(tài)采取“?！苯Y(jié)構(gòu)后備狀態(tài)少，存放效率高面臨“左遞歸”問題廣度優(yōu)先后備狀態(tài)采取“隊列”結(jié)構(gòu)后備狀態(tài)多，存放效率不高自然語言處理NLP第56頁自底向上句法分析簡單自底向上句法分析效率不高，經(jīng)常會重復嘗試相同匹配操作（回溯之前已匹配過）。一個基于圖句法分析技術（ChartParsing）被提出，它把已經(jīng)匹配過結(jié)果保留起來，今后需要時可直接使用它們，無須重新匹配。（動態(tài)規(guī)劃）自然語言處理NLP第57頁ChartParsing數(shù)據(jù)表示圖（chart）結(jié)點表示句子中詞之間位置數(shù)字非活動邊集（chart關鍵，常直接就被稱為chart）統(tǒng)計分析中規(guī)約成功所得到全部詞法/句法符號活動邊集未完全匹配產(chǎn)生式，用加小圓圈標識（o）產(chǎn)生式來表示，如：NP->ARToADJNNP->ARToN待處理表（agenda）統(tǒng)計等候加入chart已匹配成功詞法/句法符號上面活動邊、非活動邊以及詞法/句法符號都帶有“始/終止點”位置信息自然語言處理NLP第58頁“1The2cat3caught4a5mouse6”分析中數(shù)據(jù)示例1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPN(2,3)agenda56amouse自然語言處理NLP第59頁重復下面操作，直到agenda為空而且輸入中沒有下一個詞若agenda為空，則把句子中下一個詞各種詞法符號（詞性）和它們位置加入進來，從agenda中取一個元素（設為C，位置為：p1-p2)對下面形式每個規(guī)則增加活動邊：X->CX1...Xn，增加一條活動邊：X->CoX1...Xn，位置為：p1-p2；X->C，把X加入agenda，位置為：p1-p2將C作為非活動邊加入到chart位置p1-p2對已經(jīng)有活動邊進行邊擴展對每個形式為：X->X1...oC...Xn活動邊，若它在p0-p1之間，則增加一條活動邊：X->X1...Co...Xn，位置:p0-p2對每個形式為：X->X1...Xn

oC活動邊，若它在p0-p1之間，則把X加入agenda，位置為：p0-p2ChartParsing句法分析算法自然語言處理NLP第60頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARTo

NNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPART(1,2)agenda56amouse自然語言處理NLP第61頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPN(2,3)agenda56amouseNNP(1,3)自然語言處理NLP第62頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNNP(1,3)S->NPoVPNP自然語言處理NLP第63頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNV(3,4)S->NPoVPNPVP->VoNPVP(3,4)V自然語言處理NLP第64頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNS->NPoVPNPVP->VoNPVP(3,4)VVPS(1,4)自然語言處理NLP第65頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNS->NPoVPNPVP->VoNPVVPS(1,4)S自然語言處理NLP第66頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNS->NPoVPNPVP->VoNPVVPART(4,5)SNP->ARToNNP->ARToADJNART自然語言處理NLP第67頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNS->NPoVPNPVP->VoNPVVPN(5,6)SNP->ARToNNP->ARToADJNARTNNP(4,6)自然語言處理NLP第68頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNS->NPoVPNPVP->VoNPVVPSNP->ARToNNP->ARToADJNARTNNP(4,6)S->NPoVPNPVP(3,6)自然語言處理NLP第69頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNS->NPoVPNPVP->VoNPVVPSNP->ARToNNP->ARToADJNARTNS->NPoVPNPVP(3,6)VPS(1,6)自然語言處理NLP第70頁“1The2cat3caught4a5mouse6”分析過程(算法)1234ThecatcaughtARTNP->ARToNNP->ARToADJN活動邊非活動邊1.S->NPVP2.NP->ARTN3.NP->ARTADJN4.VP->V5.VP->VNPagenda56amouseNS->NPoVPNPVP->VoNPVVPSNP->ARToNNP->ARToADJNARTNS->NPoVPNPVPS(1,6)S自然語言處理NLP第71頁Proj.3實現(xiàn)一個基于簡單英語語法chart句法分析器。agenda采取棧or隊列？可能會有沒有用（不可能用到）活動邊，影響效率。自然語言處理NLP第72頁句法分析與邏輯程序設計邏輯程序設計是把程序組織成一組事實（謂詞）和一組推理規(guī)則，計算（推理）過程由實現(xiàn)系統(tǒng)自動給出，它基于謂詞演算（PredicateCalculus）進行計算。PROLOG是一個邏輯程序設計語言，在程序中，用子句（clause）描述事實和推理規(guī)則，推理過程由PROLOG執(zhí)行機制自動完成。對句法分析而言，事實：句子中每個詞詞性以及詞在句子中位置等推理規(guī)則：文法（產(chǎn)生式）自然語言處理NLP第73頁一個基于CFGPROLOG句法分析器詞典、詞形還原以及詞性標注結(jié)果可表示成事實：isart(the)isname(john)isverb(ate)isnoun(cat)......輸入句子“Johnatethecat”可表示成事實：word(john,1,2)word(ate,2,3)word(the,3,4)word(cat,4,5)自然語言處理NLP第74頁語法規(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,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)自然語言處理NLP第75頁經(jīng)過查詢謂詞s(1,5)真假來識別句子“Johnatethecat”：?-s(1,5)標準PROLOG處理策略與深度優(yōu)先自頂向下分析方法一致。自然語言處理NLP第76頁傳統(tǒng)CFG在描述自然語言時存在問題1.S->NPVP4.VP->V2.NP->ARTN5.VP->VNP3.NP->ARTADJN上面CFG描述了英語一個子集，同時，它又會生成一些不正當英語句子，如：Thestudent

solvetheproblem.（主謂不一致）Theteacherdisappearedtheproblem.（不及物動詞）自然語言處理NLP第77頁一個可能處理方案

－－增加句法符號和規(guī)則把NP分為NP-S和NP-P；把VP分成VP-S和VP-P：S->NP-SVP-SS->NP-PVP-P把N分成N-S和N-P：NP-S->ARTN-SNP-S->ARTADJN-SNP-P->ARTN-PNP-P->ARTADJN-P把V分成V-S-I、V-S-T、V-P-I和V-P-T：VP-S->V-S-IVP-S->V-S-TNP-SVP-S->V-S-TNP-PVP-P->V-P-IVP-P->V-P-TNP-SVP-P->V-P-TNP-P自然語言處理NLP第78頁增加句法符號和規(guī)則帶來問題增加了規(guī)則數(shù)量和潛在冗余類似規(guī)則缺乏關聯(lián)性對語言結(jié)構(gòu)描述缺乏深度（表層）自然語言處理NLP第79頁基于特征擴展CFG不增加原CFG中句法符號給每個句法符號增加特征（屬性），比如：NP(PER3,NUMs)//第三人稱單數(shù)VP(PER3,NUMp)//第三人稱復數(shù)特征由特征名和特征值組成。一系列特征組成了一個特征結(jié)構(gòu)（復雜特征集）。特征值能夠是普通值（原子），也能夠是另一個特征結(jié)構(gòu)，比如：NP(AGR（PER3,NUMs))，可簡寫為：NP(AGR3s)一個特征特征值能夠有多個，表示成：N(ROOTfish,AGR{3s,3p})自然語言處理NLP第80頁特征值也能夠是變量，表示取值能夠任意，比如：NP(AGR?a)表示NPAGR特征值可取任意值能夠?qū)ψ兞啃问教卣髦迪薅ǚ秶ㄊ芟拮兞浚热纾篘P(AGR?a{3s,3p})同名變量表示它們值要相同，比如：S->NP(AGR?a)VP(AGR?a)表示NP與VPAGR特征值要一致（取一樣值，主謂一致）一個規(guī)則假如包含特征值為變量成份，則該規(guī)則代表了一組規(guī)則（規(guī)則模板）。比如，上述規(guī)則代表：S->NP(AGR3s)VP(AGR3s)S->NP(AGR3p)VP(AGR3p)......自然語言處理NLP第81頁一個基于特征結(jié)構(gòu)CFG語法S->NP(AGR?a)VP(AGR?a)NP(AGR?a)->ARTN(AGR?a)NP(AGR?a)->ARTADJN(AGR?a)VP(AGR?a)->V(AGR?a,VALitr)VP(AGR?a)->V(AGR?a,VALtr)NP自然語言處理NLP第82頁合一文法一個文法能夠表示成一系列特征結(jié)構(gòu)間約束關系所組成集合。這么文法稱為合一文法（UnificationGrammar）。比如：特征結(jié)構(gòu)X0、X1和X2之間約束關系：X0->X1X2(CAT0=S,CAT1=NP,CAT2=VP,AGR0=AGR1=AGR2,VFORM0=VFORM2)它描述了基于特征CFG中一條規(guī)則：S->NP(AGR?a)VP(AGR?a)合一文法為基于特征CFG文法提供了一個形式描述基礎。特征結(jié)構(gòu)合一運算組成了合一文法基本操作，其作用有兩個：檢驗特征結(jié)構(gòu)間相容性以確定多個特征結(jié)構(gòu)是否能夠合并（規(guī)約）創(chuàng)建新特征結(jié)構(gòu)（規(guī)約結(jié)果）自然語言處理NLP第83頁合一運算特征結(jié)構(gòu)“相容”α(f)表示特征結(jié)構(gòu)α特征f值若α、β為特征結(jié)構(gòu)，對于全部特征f（屬于α或β）：若α(f)=a，β(f)=b，a、b都是原子，α和β是相容當且僅當a=b若α(f)、β(f)均為特征結(jié)構(gòu)，α和β是相容當且僅當α(f)與β(f)相容（遞歸）特征結(jié)構(gòu)“合一運算”∪：假如a、b都是原子,若a=b，則a∪b=a，不然a∪b=Φ若α、β均為特征結(jié)構(gòu)，則若α(f)=v，但β(f)未定義，則f=v屬于α∪β若β(f)=v，但α(f)未定義，則f=v屬于α∪β若α(f)=v1，β(f)=v2，且v1與v2相容，則f=(v1∪v2)屬于α∪β，不然，α∪β=Φ自然語言處理NLP第84頁合一運算舉例(CATV,ROOTcry)與(CATV,VFORMpres)

能夠合一為：(CATV,ROOTcry,VFORMpres)(CATV,AGR3s)與(CATV,AGR3p)不能合一(CATN,ROOTfish,AGR{3s,3p})與(CATN,AGR3s)

能夠合一為：(CATN,ROOTfish,AGR3s)自然語言處理NLP第85頁基于特征CFGchartparsing句子語法成份與規(guī)則匹配時，要對各個特征進行匹配和泛化處理。若規(guī)則包含特征值為變量成份，匹配時需要實例化這個規(guī)則，比如：對于規(guī)則：NP(AGR?a)->oART(AGR?a)N(AGR?a)若有下面語法成份需要匹配：ART(ROOTa,AGR3s)則需要實例化規(guī)則中?a：NP(AGR3s)->oART(AGR3s)N(AGR3s)它與ART(ROOTa,AGR3s)匹配后擴展為：NP(AGR3s)->ART(AGR3s)oN(AGR3s)若句子中還有N(ROOTdog,AGR3s)需要匹配，則深入擴展為：NP(AGR3s)->ART(AGR3s)N(AGR3s)o

自然語言處理NLP第86頁假如待匹配語法成份特征值中包含受限變量，則實例化后規(guī)則中取值范圍為二者交集，比如：實例化前規(guī)則：NP(AGR?a)->oART(AGR?a)N(AGR?a)要匹配語法成份：ART(ROOTthe,AGR?a{3s,3p})實例化后規(guī)則為：NP(AGR?a{3s,3p})->oART(AGR?a{3s,3p})N(AGR?a{3s,3p})匹配擴展后為：NP(AGR?a{3s,3p})->ART(AGR?a{3s,3p})oN(AGR?a{3s,3p})再與N(ROOTdog,AGR3s)匹配后擴展為：NP(AGR3s)->ART(AGR3s)N(AGR3s)o自然語言處理NLP第87頁句義分析句義分析目標是給出句子含義或意義(meaning)。句子意義分為：上下文無關意義上下文相關意義“Doyouknow

whatgateyouaregoingto?”意義是什么？句義分析方式先句法后語義句法語義一體化完全語義分析（無句法分析）自然語言處理NLP第88頁詞匯語義句子意義由句子中詞匯語義組合而成。句義分析首先需要處理詞匯語義表示和分析。詞匯語義表示：義項（義位）語義類義素組合自然語言處理NLP第89頁義項（義位）一個詞往往有幾個意義，每一個意義就是一個義項。比如：“明白”在《當代漢語詞典》中義項：內(nèi)容、意義等使人輕易了解；清楚；明確公開、不含糊聰明；懂道理知道；了解自然語言處理NLP第90頁語義類因為義項數(shù)量巨大，研究它們以及它們之間關系非常困難。處理這個問題一個方法是：對義項進行泛化（抽象、概括）從而形成一些語義類（類似于詞法分類－－詞性做法）。比如：把“走”、“跑”、“跳”、“爬”幾個義項泛化為語義類：“移動”。當代漢語詞林泛化問題：語義類過多會失去泛化效果。語義類過少會丟失信息。自然語言處理NLP第91頁義素（語義特征）處理義項數(shù)量巨大另一個方法是采取“義素”（語義特征）表示，義素是比義項更基本語義單位。一個義項能夠表示成義素集合（類似于句法中復雜特征集）。比如：“哥哥”義素包含：“人、親屬、同胞、年長、男性”在《知網(wǎng)》（）中用“義原”表示。義素為詞匯語義提供了更準確描述。自然語言處理NLP第92頁詞義之間關系詞義之間關系上下位關系：“動物”與“獅子”整體-部分關系：“身體”與“上肢”同義關系：“漂亮”與“漂亮”反義關系：“高”與“矮”包含關系：“兄弟”與“哥哥”和“弟弟”表示詞義之間關系另一種方式是語義場－－由幾個相互關聯(lián)詞義組成語義系統(tǒng)。例如：“師傅、徒弟”組成一個語義場“上、下、左、右”也組成一個語義場語義場確定與本體論（Ontology）有關。詞義之間關系可認為詞義之間搭配提供依據(jù)，從而為詞義消歧和句義分析提供幫助。自然語言處理NLP第93頁句義表示與分析（1）

－－邏輯形式與語義組合邏輯形式（LF，LogicalForm）用于表示上下文無關句義。它是對一階謂詞演算（FOPC）擴充，增加了一些操作和廣義量詞。比如：(DOG1FIDO1)描述了句子：Fidoisadog.(LOVES1SUE1JACK1)描述了句子：Suelovesjack.(NOT(LOVES1SUE1JACK1))描述了句子：Suedoesnotlovejack.(MOST1d1:(DOG1d1)(BARKS1d1))描述了句子：Mostdogsbark.(PRES(SEES1JOHN1FIDO1))描述了JohnseesFido.(EVERYb1:(BOY1b1)(Ad1:(DOG1d1)(LOVESb1d1)))描述了句子：Everyboylovesadog.一個意思(Ad1:(DOG1d1)(EVERYb1:(BOY1b1)(LOVESb1d1)))描述了句子：Everyboylovesadog.另一個意思(LOVES1<EVERYb1(BOY1b1)><Ad1(DOG1d1)>)描述了句子：Everyboylovesadog.兩個意思（歧義表示）自然語言處理NLP第94頁語義組合：句子語義由其成份語義組合而成。λ演算為語義組合提供了形式化計算基礎和表示。組合理論用于語義組合面臨難題：句法結(jié)構(gòu)與邏輯形式之間存在結(jié)構(gòu)上不一致對習慣用語處理（句義不由成份語義組合）帶語義解釋語法（語法/語義一體化）句法規(guī)則中加入語義特征，比如：S(...,SEM(?semvp,?semnp))->NP(...,SEM?semnp)VP(...,SEM?semvp)伴隨句法規(guī)則給出句法符號語義描述和計算規(guī)則自然語言處理NLP第95頁句義表示與分析（2）

－－論旨角色與格語法論旨角色（thematicrole）或格角色（caserole）基于動詞給出句子中其它成份與它淺層語義關系，比如：Theboyopenedthedoorwithakey.theboy:AGENT（施事格）thedoor:OBJECT（客體格）akey:INSTUMENT（工具格）自然語言處理NLP第96頁格語法格語法由美國語言學家CharlesJ.Fillmore提出用于對句法結(jié)構(gòu)與語義之間關系進行描述理論?！癟owardsamoderntheoryofcase”、“Thecaseforcase”、“Someproblemsforcasegrammar”基本語義規(guī)則S->M+P一個句子（S）由情態(tài)（M）和命題（P）組成。情態(tài)包含：時體態(tài)、語氣以及否定等。P->V+C1+C2+...+Cn命題由動詞（V）及若干格短語（C1~Cn）組成。Ci->Ki+NPi格短語由格標識（K）和名詞短語（NP）組成。提供從表層格到深層格轉(zhuǎn)換規(guī)則自然語言處理NLP第97頁格種類：施事格(Agentive)：Helaughed.工具格(Instrumental)：Hecuttheropewithaknife.與格(Dative)：Hegivesmeaball.使成格(Factitive)：JohndreamedadreamaboutMary.方位格(Locative)：Heisinthehouse.客體格(Objective):Heboughtabook.受益格(Benefective):HesangasongforMary.源點格(Source):IboughtabookfromMary.終點格(Goal):IsoldacartoMary.伴隨格(Comitative):HesangasongwithMary.......（有多少格?）自然語言處理NLP第98頁動詞格框架詞典中對每個動詞需給出：它所允許格，包含它們性質(zhì)（必需、禁止、自由）這些格特征（從屬詞、中心詞語義信息等）自然語言處理NLP第99頁基于格語法語義分析基于信息格標識體系動詞格框架名詞語義信息分析過程格短語及主動詞識別利用主動詞格框架確定格短語格。分析結(jié)果：句子格框架。自然語言處理NLP第100頁基于格語法語義分析結(jié)果（例）Intheroom,hebrokeawindowwithahammer.[BREAK[case-frameagentive:HEobjective:WINDOWinstrumental:HAMMERlocative:ROOM][modalstime:pastvoice:active]]自然語言處理NLP第101頁機器翻譯自然語言處理NLP第102頁機器翻譯歷史1947，WarrenWeaver’smemo1954，第一個公開展示俄英MT原型系統(tǒng)1966，美國科學院ALPAC匯報宣告機器翻譯走入低谷1970s，Systran（1970），Meteo（1976），Early1980s，復蘇，Eurotra、Mu、...Late1980s~early1990s，商品化系統(tǒng)投入市場，語音翻譯和統(tǒng)計機器翻譯（SMT）出現(xiàn)Late1990s，Internet加速了MT，MAT、EBM