知識(shí)圖譜-第9章-知識(shí)推理

第九章：知識(shí)推理《知識(shí)圖譜》配套講義1提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)2提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)3作為知識(shí)載體的知識(shí)圖譜物理世界人類世界機(jī)器世界能理解言外之意；能創(chuàng)造新說法和新語法；語言系統(tǒng)語言理解與語言生成知識(shí)圖譜能不能舉一反三，自動(dòng)發(fā)現(xiàn)新知識(shí)？知識(shí)表示與知識(shí)推理4作為認(rèn)知智能重要基礎(chǔ)的知識(shí)圖譜知其然的AI

vs

知其所以然的AI人的大腦依賴所學(xué)的知識(shí)進(jìn)行思考、邏輯推理、理解語言知識(shí)圖譜感知識(shí)別判斷思考推理生成深度學(xué)習(xí)學(xué)習(xí)有智慧的AI有知識(shí)的AI推理5基于知識(shí)的Agent人類認(rèn)識(shí)世界，這種認(rèn)識(shí)能幫助我們做事。也稱認(rèn)識(shí)論、知識(shí)論，相對(duì)應(yīng)的是行為論。---認(rèn)知論人類一直強(qiáng)調(diào)人的智能是如何獲得的：不是靠反射機(jī)制而是對(duì)知識(shí)的內(nèi)部表示進(jìn)行操作的推理過程。---基于知識(shí)的Agent領(lǐng)域無關(guān)的算法特定領(lǐng)域的內(nèi)容推理引擎知識(shí)庫6知識(shí)推理示例：渡河背景：一個(gè)人帶著一匹狼、一只羊和一捆卷心菜來到了河邊。他需要過河，但是河邊只有一條船，而且他只能帶一樣?xùn)|西上船。他不能把狼和羊一起留在河邊，也不能讓羊和卷心菜一起留在河邊，因?yàn)樵谶@兩種情況下，前者都會(huì)吃掉后者。提問：如何用最少的渡河次數(shù)把所有東西都帶到河對(duì)岸？

背景：獅子、老虎、熊三對(duì)動(dòng)物過河，每種動(dòng)物有媽媽和孩子兩個(gè)（就是獅子?jì)寢?、小獅子；老虎媽媽、小老虎；熊媽媽、小熊）。而小動(dòng)物的媽媽不在的話，自己就會(huì)被吃掉（例如老虎媽媽不在，小老虎會(huì)被獅子?jì)寢尰蛐軏寢尦缘簦Ｋ械膵寢尪紩?huì)劃船，孩子里面只有小獅子會(huì)劃船。一艘船上只能同時(shí)最多坐兩個(gè)動(dòng)物（可以是兩個(gè)媽媽。提問：請(qǐng)問他們要如何過河才能保全所有的動(dòng)物？7知識(shí)推理示例：Wumpus世界（1）來自書籍《ArtificialIntelligence:AModernApproach(4thEdition)》Wumpus世界是一個(gè)由多個(gè)房間組成并連接起來的山洞。在洞穴的某處隱藏著一只怪獸(Wumpus)，它會(huì)吃掉進(jìn)入它房間的任何人。探險(xiǎn)者(Agent)可以射殺怪獸，但是探險(xiǎn)者只有一支箭。某些房間是無底洞，任何人漫游到這些房間都會(huì)被無底洞吞噬。生活在該環(huán)境下的唯一希望是存在發(fā)現(xiàn)一堆金子的可能性。性能度量：帶著金子爬出洞口+1000，掉入洞被Wumpus吃-1000，采用一個(gè)行動(dòng)-1，用掉箭-10。Agent死亡或出洞，則游戲結(jié)束。環(huán)境：4*4房間網(wǎng)格，始發(fā)[1,1]且向右。1個(gè)Wumpus，1/5房間為無底洞，分布均勻。執(zhí)行器：Agent向前、左轉(zhuǎn)、右轉(zhuǎn)、射箭。8知識(shí)推理示例：Wumpus世界（2）傳感器：在與無底洞相鄰的方格內(nèi)，Agent能感知到微風(fēng)（Breeze）；在與Wumpus相鄰的方格內(nèi)，Agent能感受到臭氣（Stench）；在金子所處方格，Agent能感受到閃閃金光（Glitter）；當(dāng)Agent碰到墻時(shí)，它感知到碰撞（Bump）；當(dāng)Wumpus被殺死后，它發(fā)出的嚎叫聲（Scream）。9知識(shí)推理示例：Wumpus世界（3）第1步感知：NONE[1,2]和[2,1]安全第2步感知：微風(fēng)[2,2]或[3,1]洞

回到[1,1]然后去[1,2]10知識(shí)推理示例：Wumpus世界（4）第3步感知：臭氣[1,3]怪獸和[2,2]安全

射殺怪獸,去往[2,2]第5步感知：臭氣，閃光，微風(fēng)[2,3]金子，[2,4]或[3,3]洞

拿金子,往回走11什么是推理（1）推理是邏輯學(xué)、哲學(xué)、心理學(xué)、人工智能等學(xué)科中的重要概念。早在古希臘時(shí)期，著名哲學(xué)家亞里斯多德就提出三段論作為現(xiàn)代演繹推理的基礎(chǔ)。在計(jì)算機(jī)科學(xué)及人工智能領(lǐng)域，推理是一個(gè)按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過程。推理就是通過已知知識(shí)推斷出未知知識(shí)的過程。12什么是推理（2）推理，邏輯學(xué)中指思維的基本形式之一，是由一個(gè)或幾個(gè)已知的判斷（前提）推出新判斷（結(jié)論）的過程，有直接推理、間接推理等。------《現(xiàn)代漢語詞典第6版》事件必定有其原因，事件背后必定有其真相。通過推理可以預(yù)測(cè)未來，甚至確定未來發(fā)展的詳細(xì)過程。任何一個(gè)推理都包含已知判斷、新的判斷和一定的推理形式。作為推理的已知判斷叫前提，根據(jù)前提推出新的判斷叫結(jié)論。前提與結(jié)論的關(guān)系是理由與推斷，原因與結(jié)果的關(guān)系。13什么是推理（3）牛頓的出生地屬于哪個(gè)國家已知知識(shí)：事實(shí)公理常識(shí)…未知知識(shí)：新事實(shí)新公理新常識(shí)…演繹、歸納、朔因預(yù)測(cè)、推斷、類比14提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)15知識(shí)推理的分類歸納推理與演繹推理歸納推理(induction)：歸納是從特殊到一般的過程。所謂歸納推理，就是從一類事物的大量特殊事例出發(fā)，去推出該類事物的一般性結(jié)論。我們熟知的數(shù)學(xué)歸納法就是歸納推理的一個(gè)典型例子。前提：藍(lán)鯨可以噴射水柱。抹香鯨可以噴射水柱。座頭鯨可以噴射水柱。結(jié)論：鯨魚都可以噴射水柱。前提：樹木有年輪。烏龜有年輪（龜甲上的環(huán)數(shù)）。牛馬有年輪（年輪在牙齒上）。結(jié)論：所有生物都有記錄自己壽命長(zhǎng)短的年輪。日本科學(xué)家發(fā)現(xiàn)，人的年輪在腦中。16知識(shí)推理的分類歸納推理與演繹推理演繹推理(deduction)：演繹是從一般到特殊的過程。所謂演繹推理，就是從一般性的前提出發(fā)，通過演繹（即推導(dǎo)），得出具體陳述或個(gè)別結(jié)論的過程。最經(jīng)典的演繹推理就是三段論(syllogism)，它包括一個(gè)一般性原則（大前提）、一個(gè)附屬于大前提的特殊化陳述（小前提），以及由此引申出的特殊化陳述符合一般性原則的結(jié)論。大前提：人工智能學(xué)院的學(xué)生都會(huì)PyTorch。小前提：小李是人工智能學(xué)院的學(xué)生。結(jié)論：小李會(huì)PyTorch。17知識(shí)推理的分類歸納推理與演繹推理演繹推理(deduction)：演繹推理不僅僅局限于三段論，也不只是從一般到特殊的過程。它有著強(qiáng)烈的演繹特性，重在通過利用每一個(gè)證據(jù)，逐步地推導(dǎo)到目標(biāo)或以外的結(jié)論，多被用于數(shù)學(xué)物理證明、思維推導(dǎo)等各類應(yīng)用。例：莎士比亞在《威尼斯商人》中，描寫富家少女鮑西亞品貌雙全，貴族子弟、公子王孫紛紛向她求婚。鮑西亞按照其父遺囑，由求婚者猜盒訂婚。鮑西亞有金、銀、鉛三個(gè)盒子，分別刻有三句話，其中只有一個(gè)盒子放有鮑西亞的肖像。求婚者中誰通過這三句話，最先猜中肖像放在哪個(gè)盒子里，誰就可以娶到鮑西亞。

金盒子上說：“肖像不在此盒中?！?/p>

銀盒子上說：“肖像在鉛盒中。”

鉛盒子上說：“肖像不在此盒中。”鮑西亞告訴求婚者，上述三句話中，最多只有一句話是真的。如果你是一位求婚者，如何盡快猜中鮑西亞的肖像究竟放在哪一個(gè)盒子里？18知識(shí)推理的分類歸納推理與演繹推理的區(qū)別演繹推理是在已知領(lǐng)域內(nèi)的一般性知識(shí)的前提下，求解一個(gè)具體問題或者證明一個(gè)結(jié)論的正確性。演繹推理得出的結(jié)論實(shí)際上早已蘊(yùn)含在一般性知識(shí)的前提中，演繹推理只不過是將已有事實(shí)揭示出來，因此它不能增殖新知識(shí)。相反，歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的。這種由個(gè)別事物或現(xiàn)象推出一般性知識(shí)的過程，是增殖新知識(shí)的過程。19知識(shí)推理的分類必然性推理與或然性推理：必然性推理前提與結(jié)論有必然性聯(lián)系，即前提蘊(yùn)含結(jié)論。在必然性推理中，前提真而結(jié)論假是不可能的，即把對(duì)前提的肯定與對(duì)結(jié)論的否定結(jié)合起來就會(huì)產(chǎn)生矛盾。傳統(tǒng)邏輯中通過直言命題變形的直接推理（換質(zhì)法、換位法推理等）、通過命題間對(duì)應(yīng)關(guān)系所進(jìn)行的直接推理、三段論推理、各種假言推理、選言推理以及完全歸納推理等等，都屬于必然性推理。20知識(shí)推理的分類必然性推理與或然性推理：或然性推理前提與結(jié)論無蘊(yùn)含關(guān)系。或然性推理中，前提真而結(jié)論假并非完全不可能，將對(duì)前提的肯定與對(duì)結(jié)論的否定結(jié)合起來并不產(chǎn)生矛盾。簡(jiǎn)單枚舉歸納推理、類比推理、回溯推理等等都屬于或然性推理。例如，前提P只是結(jié)論C的“疑似”必要條件。P：房間里有物品

C：房子會(huì)著火21知識(shí)推理的分類單調(diào)推理與非單調(diào)推理：?jiǎn)握{(diào)推理單調(diào)推理是指在推理過程中隨著推理的向前推進(jìn)以及新知識(shí)的加入，推出的結(jié)論呈單調(diào)增加的趨勢(shì)并越來越接近最終目標(biāo)，且在推理過程中不會(huì)出現(xiàn)反復(fù)的情況，即不會(huì)因新知識(shí)的加入而否定前面推出的結(jié)論，從而使推理又退回到前面的某一步。一般情況下考慮單調(diào)推理，大部分書籍和我們的課程都只考慮單調(diào)推理。22知識(shí)推理的分類單調(diào)推理與非單調(diào)推理：非單調(diào)推理非單調(diào)推理是指在推理過程中，由于新知識(shí)的加入，不僅沒有加強(qiáng)已經(jīng)推出的結(jié)論，反而要否定它，使其需要退回到之前步驟。通常是在知識(shí)不完備的情況下發(fā)生，該種情況下需要先做某些假設(shè)，并在此假設(shè)下進(jìn)行推理；隨著新知識(shí)的加入可能會(huì)發(fā)現(xiàn)原假設(shè)不正確。人們?nèi)粘Ｉ钪泻芏嗤评矶际欠菃握{(diào)推理，例如，鴕鳥在原野上飛馳（默認(rèn)以為所有鳥都會(huì)飛），只有看到它是奔跑，才能推斷它不是在飛。23知識(shí)推理的分類缺省推理也稱默認(rèn)推理，它是在知識(shí)不完全的情況下作出的推理，通常的形式：如果沒有足夠的證據(jù)證明結(jié)論不成立，則認(rèn)為結(jié)論是正確的。溯因推理也稱反繹推理、反向推理，是推理到最佳解釋的過程。它是開始于事實(shí)的集合，并推導(dǎo)出其最佳解釋的推理過程。溯因（abduction）意味生成假設(shè)來解釋觀察或結(jié)論。24知識(shí)推理的分類確定性推理與不確定性推理：確定性推理確定性推理大多指確定性邏輯推理，它具有完備的推理過程和充分的表達(dá)能力，可以嚴(yán)格地按照專家預(yù)先定義好的規(guī)則準(zhǔn)確地推導(dǎo)出最終結(jié)論。但是確定性推理很難應(yīng)對(duì)真實(shí)世界中，尤其是存在于網(wǎng)絡(luò)大規(guī)模知識(shí)圖譜中的不確定甚至不正確的事實(shí)和知識(shí)。不確定的知識(shí)：“一個(gè)人和其父親擁有同樣的國籍”這條規(guī)則在現(xiàn)實(shí)生活中大部分情況下都是正確的，但也不排除移民、母方國籍等因素使得少量事實(shí)不滿足它。不正確的事實(shí)：“美國的首都是紐約”這個(gè)事實(shí)是錯(cuò)誤的，大規(guī)模知識(shí)圖譜YAGO抽樣統(tǒng)計(jì)中有5%左右的錯(cuò)誤事實(shí)。25知識(shí)推理的分類確定性推理與不確定性推理：不確定性推理不確定性推理也被稱為概率推理，是統(tǒng)計(jì)機(jī)器學(xué)習(xí)中一個(gè)重要的議題。它并不是嚴(yán)格地按照規(guī)則進(jìn)行推理，而是根據(jù)以往的經(jīng)驗(yàn)和分析，結(jié)合專家先驗(yàn)知識(shí)構(gòu)建概率模型，并利用統(tǒng)計(jì)計(jì)數(shù)、最大化后驗(yàn)概率等統(tǒng)計(jì)學(xué)習(xí)的手段對(duì)推理假設(shè)進(jìn)行驗(yàn)證或推測(cè)。不確定性推理可以有效建模真實(shí)世界中的不確定性。權(quán)重推理規(guī)則0.9???,??:(??,child_of,??)?(??,parent_of,??)0.8???,??,??:

(??,born_in,??)?(??,city_of,??)?(??,nationality,??)0.5???,??,??:

(??,child_of,??)?(??,child_of,??)?(??,sister_of,??)……26知識(shí)推理的分類邏輯推理和非推理推理邏輯推理：過程包含了嚴(yán)格的約束和推理過程（研究較多）。非邏輯推理：自然語言推理，推理過程相對(duì)模糊。符號(hào)推理與數(shù)值推理符號(hào)推理：符號(hào)推理的特點(diǎn)就是在知識(shí)圖譜中的實(shí)體和關(guān)系符號(hào)上直接進(jìn)行推理。確定性和不確定性邏輯推理都屬于符號(hào)推理。數(shù)值推理：與符號(hào)推理相對(duì)的就是數(shù)值推理。數(shù)值推理就是使用數(shù)值計(jì)算，尤其是向量矩陣計(jì)算的方法，捕捉知識(shí)圖譜上隱式的關(guān)聯(lián)，模擬推理的進(jìn)行。本課程介紹的數(shù)值推理方法一般指基于分布式知識(shí)表示的推理（神經(jīng)網(wǎng)絡(luò)方法）。27概括：推理方式及其分類參考書籍《知識(shí)表示與處理》推理方式按前提與結(jié)論的聯(lián)系性質(zhì)劃分按新知識(shí)推出途徑劃分按知識(shí)確定性劃分按推理過程單調(diào)性劃分按實(shí)現(xiàn)技術(shù)劃分演繹推理歸納推理朔因推理缺省推理必然性推理或然性推理確定性推理不確定性推理單調(diào)推理非單調(diào)推理基于符號(hào)演算的推理基于數(shù)值計(jì)算的推理28提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)29知識(shí)圖譜補(bǔ)全不完備的知識(shí)圖譜：實(shí)體缺失、事實(shí)缺失等對(duì)于世界中存在的2百多萬部電影，DBpedia和Freebase中只分別記錄了78萬和26萬部；在DBpedia和Freebase中，分別有40.7%和72.2%的人物沒有記錄“出生地”信息，有90.8%和75.5%的人物沒有記錄“國籍”信息。據(jù)統(tǒng)計(jì)，知識(shí)圖譜DBpedia在2016年到2017年間，1年時(shí)間新增了近37萬實(shí)體和146萬事實(shí)。知識(shí)圖譜補(bǔ)全：也稱知識(shí)圖譜上的鏈接預(yù)測(cè)，其本質(zhì)是根據(jù)知識(shí)庫中已有的知識(shí)推斷出新的、未知的知識(shí)。知識(shí)庫補(bǔ)全可以用來建立更全面的知識(shí)庫，是知識(shí)庫構(gòu)建的重要手段之一。30知識(shí)問答基于知識(shí)推理的深度問答問答系統(tǒng)是自然語言處理領(lǐng)域一個(gè)重要的發(fā)展方向，通過自然語言的方式來獲取知識(shí)。在很多真實(shí)應(yīng)用場(chǎng)景下，問答系統(tǒng)能夠帶來極大的知識(shí)獲取的便利性。但除了簡(jiǎn)單地檢索實(shí)體，更多的問題要求問答系統(tǒng)具有知識(shí)推理的能力?；谥R(shí)推理的問答系統(tǒng)：如將TransE向量空間與搜索技術(shù)結(jié)合?；?qū)⒅R(shí)推理等技術(shù)直接應(yīng)用于問答系統(tǒng)：如用R-GCN來建模多輪對(duì)話問答系統(tǒng)的對(duì)話結(jié)構(gòu)和背景知識(shí)。31搜索與推薦基于知識(shí)圖譜的搜索搜索直達(dá)目標(biāo)是搜索系統(tǒng)的核心需求。在知識(shí)圖譜的支撐下，搜索系統(tǒng)越來越智能化，集中體現(xiàn)在對(duì)搜索意圖的準(zhǔn)確理解以及對(duì)搜索結(jié)果的精準(zhǔn)匹配上。實(shí)體搜索主要分為搜索意圖理解，目標(biāo)查找，結(jié)果呈現(xiàn)和實(shí)體探索。例如，系統(tǒng)可以借助知識(shí)圖譜，理解用戶想搜索的是網(wǎng)球明星李娜，而不是歌星李娜，從而實(shí)現(xiàn)準(zhǔn)確的意圖理解。此外，還可以拓展搜索結(jié)果，呈現(xiàn)“李娜”的相關(guān)實(shí)體。在Google上還會(huì)顯示“李娜”知識(shí)卡片。基于準(zhǔn)確搜索意圖理解的精確匹配擴(kuò)展的搜索結(jié)果來自Google知識(shí)圖譜的“李娜”知識(shí)卡片32提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)33演繹推理：推理具體事實(shí)34演繹推理：推理具體事實(shí)35提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)36邏輯推理/邏輯學(xué)（Logics）

37蘊(yùn)含（Entailment）

38回到Wumpus世界[1,1]感知NONE[2,1]感知微風(fēng)系統(tǒng)（Agent）想知道未探索的鄰近房間[1,2][2,2][3,1]是否包含洞39Wumpus世界

40邏輯推理算法

41命題邏輯：語法命題邏輯是一種簡(jiǎn)單邏輯命題符號(hào)P、Q、R、P22等是語句IfSisasentence,

Sisasentence(negation/非)IfS1andS2aresentences,S1

S2isasentence(conjunction/合取)IfS1andS2aresentences,S1

S2isasentence(disjunction/析取)IfS1andS2aresentences,S1

S2isasentence(implication/蘊(yùn)含)IfS1andS2aresentences,S1

S2isasentence(biconditional)42命題邏輯：語義

43邏輯等價(jià)（Logicalequivalence）如果在相同模型中真值相同，則兩個(gè)語句是邏輯等價(jià)的：α≡βiffα╞βandβ╞α44有效性和可滿足性

45推導(dǎo)與證明：基本推理規(guī)則假言推理規(guī)則（ModusPonens）:消去合取詞（And-Elimination）:其他規(guī)則:46Wumpus世界的語句

47Wumpus世界的推理

48歸結(jié)（Resolution）證明

P1,3

P2,2,

P2,2P1,349轉(zhuǎn)換為合取范式（CNF）合取范式(ConjunctiveNormalForm,CNF)子句為合取式表達(dá)，每個(gè)子句為文字的析取式(A

B)

(B

C

D)如何轉(zhuǎn)換為合取范式：以B1,1

(P1,2

P2,1)為例消去等價(jià)詞

,

替換α

β為(α

β)

(β

α).(B1,1

(P1,2

P2,1))

((P1,2

P2,1)

B1,1)2.消去蘊(yùn)含詞

,替換α

β為

α

β.(

B1,1

P1,2

P2,1)

(

(P1,2

P2,1)

B1,1)3.將否定詞

內(nèi)移：使用deMorgan'srules和

double-negation.(

B1,1

P1,2

P2,1)

((

P1,2

P2,1)

B1,1)4.使用分配律，在可能的位置上將

對(duì)

進(jìn)行分配.(

B1,1

P1,2

P2,1)

(

P1,2

B1,1)

(

P2,1

B1,1)50歸結(jié)算法，歸結(jié)推理/證明

第一行為合取范式，第二行為對(duì)第一行的歸結(jié)結(jié)果51歸結(jié)演繹推理示例請(qǐng)寫出下面推理的證明過程事實(shí)：如果今天是下雨天，則要帶雨傘或帶雨衣。如果走路上班，則不帶雨衣。問題：今天下雨，走路上班，所以帶傘。進(jìn)行如下定義：P:今天下雨；Q:帶雨傘；R:帶雨衣；S:走路上班。證明：將已知事實(shí)及問題用命題公式表示出來R1:如果今天是下雨天，則要帶雨傘或帶雨衣。命題公式：P(Q

R)合取范式：

P

QRR2:如果走路上班，則不帶雨衣。命題公式：S

R合取范式：

S

RR3：今天下雨，走路上班，所以帶傘。命題公式：P∧S

Q合取范式：

P

SQ結(jié)論取反：P

SQ參考書籍《知識(shí)表示與處理》歸結(jié)過程：(1)

P

QR(2)

S

R(3)P(4)S(5)Q(6)

R---(2)與(4)(7)

P---(1)(5)與(6)(8)None---(3)與(7)52推理算法：前向鏈接和反向鏈接算法Horn形式（受限形式的一種）KB=Horn子句的合取Horn子句：至多只有一個(gè)正文字的析取式例如，?L1,1

?Breeze

B1,1,L1,1

Breeze

B1,1α1

…

αn

β

中

前的為前提（premise）,后的為結(jié)論（conclusion）對(duì)于Horn形式的假言推理：使用Horn子句的推理可以使用前向鏈接（forwardchaining）和反向鏈接（backwardchaining）算法這兩種算法都很自然，易于理解，且是線性運(yùn)行時(shí)間α1,…,αn, α1

…

αn

ββ53前向鏈接（Forwardchaining）基本思想：找到前件（premise）能夠被KB滿足的規(guī)則把推理結(jié)論添加到KB中，直到查詢被發(fā)現(xiàn)Horn子句集合對(duì)應(yīng)的AND–OR圖54前向鏈接（Forwardchaining）主要步驟統(tǒng)計(jì)子句中未知前件的個(gè)數(shù)（計(jì)數(shù)）如果前件已知，則減去未知個(gè)數(shù)數(shù)量當(dāng)數(shù)量為0時(shí)，結(jié)論作為已知事實(shí)添加到KB中為了避免冗余推理，還可記錄推理結(jié)論55前向鏈接的完備性

56反向鏈接（Backwardchaining）基本思路：從查詢Q反向工作檢查Q是否已知，如果已知，則返回否則，檢測(cè)能推導(dǎo)出Q的規(guī)則（rules），反復(fù)應(yīng)用反向鏈接證明它們的前件（premises）需要避免循環(huán)：檢查新的子目標(biāo)1）是否已經(jīng)被證明為真2）是否已經(jīng)證明失敗57前向鏈接vs.反向鏈接時(shí)間復(fù)雜度都是與KB的規(guī)模線性相關(guān)前向鏈接是數(shù)據(jù)驅(qū)動(dòng)（data-driven）反向鏈接是任務(wù)驅(qū)動(dòng)（goal-driven）前向鏈接算法可能生成很多與目標(biāo)無關(guān)的結(jié)論一般來說，反向鏈接算法更適合用來解決具體問題反向鏈接算法的時(shí)間復(fù)雜度一般比KG的線性規(guī)模要小得多58提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)59基于產(chǎn)生式規(guī)則的推理產(chǎn)生式系統(tǒng)一種前向推理系統(tǒng)，可以按照一定機(jī)制執(zhí)行規(guī)則從而達(dá)到某些目標(biāo)典型應(yīng)用：專家系統(tǒng)（如診斷感染性疾病的專家系統(tǒng)MYCIN）產(chǎn)生式系統(tǒng)的組成事實(shí)集合（WorkingMemory）產(chǎn)生式/規(guī)則集合推理引擎本節(jié)內(nèi)容大部分參考書籍《知識(shí)圖譜導(dǎo)論》控制策略規(guī)則集合推理引擎事實(shí)集合60基于產(chǎn)生式規(guī)則的推理事實(shí)集合/運(yùn)行內(nèi)存（WorkingMemory,WM）事實(shí)的集合用于存儲(chǔ)當(dāng)前系統(tǒng)中的所有事實(shí)事實(shí)描述對(duì)象，如(studentname:Aliceage:24)描述關(guān)系，如(olderThanJohnAlice)產(chǎn)生式集合(ProductionMemory,PM)產(chǎn)生式（推理規(guī)則）的集合產(chǎn)生式IFconditionsTHENactionsconditions是由條件組成的集合，又稱為L(zhǎng)HS（LeftHandSide）actions是由動(dòng)作組成的序列，又稱為RHS（RightHandSide)61產(chǎn)生式規(guī)則：LeftHandSideLHS條件（condition）的集合，各條件之間是且的關(guān)系當(dāng)LHS中的所有條件均被滿足，則該規(guī)則觸發(fā)每個(gè)條件形如(typeattr1:spec1…

attrn:specn)speci表示對(duì)attri的約束，形式可取下面種類原子，如：Alice(personname:Alice)用于判斷取值是否為Alice變量，如：x(personname:x)用于判斷取值是否為x(如果未綁定常量，則視為自由變量）表達(dá)式，如[n+4]（personage:[n+4])用于判斷取值是否等于（需事先賦值）布爾測(cè)試，如{>10}(personage:{>10})用于判斷取值是否滿足條件約束的與、或、非操作62產(chǎn)生式規(guī)則：RightHandSideRHS動(dòng)作(action)的序列，執(zhí)行時(shí)依次執(zhí)行動(dòng)作的種類如下：ADDpattern向事實(shí)集合WM中加入形如pattern的事實(shí)REMOVEi從事實(shí)集合WM中移除當(dāng)前規(guī)則第i個(gè)條件匹配的事實(shí)MODIFYi(attrspec)對(duì)于當(dāng)前規(guī)則第i個(gè)條件匹配的事實(shí)，將其對(duì)應(yīng)于attr屬性的值改為spec63產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則IFconditionsTHENactions示例1：IF（Student姓名:XYZ）ThenADD(Person姓:X)如果有個(gè)學(xué)生名為XYZ，那么向事實(shí)集合中加入一個(gè)事實(shí)，表示有一個(gè)姓X的人。示例2（來自MYCIN專家系統(tǒng)，RULE047）：IF($AND(NotDefiniteCntxtIdent)#病原體的鑒別名不確定，且 (SAMECntxtSiteBlood)#病原體來自血液，且 (SAMECntxtStainGramneg)#病原體的染色是革蘭氏陰性，且 (SAMECntxtMorphRod)#病原體的形態(tài)是桿狀的，且 (SAMECntxtBurnt)#病原體呈褐色，且Then(CntxtIdentPseudomonasTally.4)#病原體的鑒別名是假單胞細(xì)菌，可信度為0.464推理引擎該步驟是產(chǎn)生式系統(tǒng)的核心，用于控制系統(tǒng)的執(zhí)行模式匹配用規(guī)則的條件部分匹配事實(shí)集中的事實(shí)，整個(gè)LHS都被滿足的規(guī)則被觸發(fā)，并被加入議程(agenda)沖突消解按一定的策略從被觸發(fā)的多條規(guī)則中選擇一條規(guī)則執(zhí)行執(zhí)行被選擇出來的規(guī)則的RHS，從而對(duì)WM進(jìn)行一定的操作產(chǎn)生式系統(tǒng)=事實(shí)集合+產(chǎn)生式集合+推理引擎65產(chǎn)生式系統(tǒng)執(zhí)行流程模式匹配產(chǎn)生式規(guī)則庫WM(事實(shí)集合)沖突規(guī)則集推理控制沖突消解規(guī)則觸發(fā)規(guī)則執(zhí)行產(chǎn)生式系統(tǒng)的工作周期控制系統(tǒng)進(jìn)行的一次推理過程從產(chǎn)生式規(guī)則庫中取一條規(guī)則，將其前提同當(dāng)前WM中的事實(shí)/數(shù)據(jù)進(jìn)行模式匹配是否匹配成功把該規(guī)則的結(jié)論放入當(dāng)前WM，或者執(zhí)行規(guī)則所規(guī)定的動(dòng)作是否66模式匹配：Rete算法Rete算法是產(chǎn)生式規(guī)則系統(tǒng)中常用的推理算法核心思想：將產(chǎn)生式規(guī)則中的LHS部分組織成判別網(wǎng)絡(luò)，然后用分類的匹配項(xiàng)構(gòu)造匹配網(wǎng)絡(luò)，同時(shí)緩存中間結(jié)果。以空間換時(shí)間的做法Rete算法基本過程

網(wǎng)絡(luò)用來檢驗(yàn)和保存規(guī)則集合中每條規(guī)則所對(duì)應(yīng)的條件集合。

網(wǎng)絡(luò)用來保存Join計(jì)算的中間結(jié)果。WorkingMemory中的所有事實(shí)首先與

網(wǎng)絡(luò)中的元素進(jìn)行匹配，然后按照網(wǎng)絡(luò)的結(jié)構(gòu)形式完成Join操作，將Join的中間結(jié)果保存于

網(wǎng)絡(luò)中，最終結(jié)果加入agenda中。67沖突消解解決沖突：匹配成功的規(guī)則可能不止一條從被觸發(fā)的多條規(guī)則中選擇一條注：在具體場(chǎng)景中，被觸發(fā)的多條規(guī)則可全被執(zhí)行常見策略隨機(jī)選擇：從被觸發(fā)的規(guī)則中隨機(jī)選擇一條執(zhí)行具體性（specificity）：選最具體的規(guī)則(studentname:x)…(studentname:xage:20)…新近程度(recency)：選擇最近沒有被觸發(fā)的規(guī)則68提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)69基于元知識(shí)（規(guī)則）進(jìn)行推理核心挑戰(zhàn)：如何利用不確定性的元知識(shí)進(jìn)行聯(lián)合推理

5.0

兒子(X,Y)∧國籍(Y,Z)?國籍(X,Z)5.0

工作地(X,Y)∧國家(Y,Z)?國籍(X,Z)10.0

出生地(X,Y)∧國家(Y,Z)?國籍(X,Z)10.0

出生地(X,Y)∧語言(Y,Z)?母語(X,Z)70馬爾可夫邏輯網(wǎng)馬爾可夫邏輯網(wǎng)(MarkovLogicNetwork)[RichardsonandDomingos,2006]

是將概率圖模型與一階謂詞邏輯相結(jié)合的一種統(tǒng)計(jì)關(guān)系學(xué)習(xí)模型，其核心思想是通過為規(guī)則綁定權(quán)重的方式將一階謂詞邏輯規(guī)則中的硬性約束（hardconstraints）進(jìn)行軟化。1）一階謂詞邏輯知識(shí)庫可看作是在一個(gè)可能世界的集合上建立一系列硬性規(guī)則，即如果一個(gè)世界違反了其中的某一條規(guī)則，那么這個(gè)世界的存在概率即為零。2）馬爾可夫邏輯網(wǎng)的基本思想是讓那些硬性規(guī)則有所松弛，即當(dāng)一個(gè)世界違反了其中的一條規(guī)則，那么這個(gè)世界存在的可能性將降低，但并非不可能。一個(gè)世界違反的規(guī)則越少，那么這個(gè)世界存在的可能性就越大。71馬爾可夫邏輯網(wǎng)馬爾可夫邏輯網(wǎng)(MarkovLogicNetwork)[RichardsonandDomingos,2006]

是將概率圖模型與一階謂詞邏輯相結(jié)合的一種統(tǒng)計(jì)關(guān)系學(xué)習(xí)模型，其核心思想是通過為規(guī)則綁定權(quán)重的方式將一階謂詞邏輯規(guī)則中的硬性約束（hardconstraints）進(jìn)行軟化。3）為此，馬爾可夫邏輯網(wǎng)給每條規(guī)則都加上一個(gè)特定的權(quán)重來反映其約束強(qiáng)度。規(guī)則的權(quán)重越大，其約束能力越強(qiáng)，即對(duì)于滿足和不滿足該規(guī)則的兩個(gè)世界而言，它們之間的差異將越大。當(dāng)規(guī)則的權(quán)重設(shè)置為無窮大時(shí)，其退化為硬性規(guī)則。72馬爾可夫邏輯網(wǎng)綁定權(quán)重的規(guī)則示例這些規(guī)則在現(xiàn)實(shí)世界中通常是真的，但不總是真的，并且它們有著不同的成立概率。73馬爾可夫邏輯網(wǎng)馬爾可夫邏輯網(wǎng)形式化定義

74馬爾可夫邏輯網(wǎng)

75馬爾可夫邏輯網(wǎng)從馬爾可夫邏輯網(wǎng)的定義出發(fā)，很容易得到一個(gè)圖結(jié)構(gòu)：每個(gè)原子事實(shí)對(duì)應(yīng)于圖中的一個(gè)節(jié)點(diǎn)。當(dāng)兩個(gè)節(jié)點(diǎn)所表示的原子事實(shí)出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中時(shí)，這兩個(gè)節(jié)點(diǎn)之間存在一條邊。所有出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中的原子事實(shí)組成了一個(gè)團(tuán)。76馬爾可夫邏輯網(wǎng)從馬爾可夫邏輯網(wǎng)的定義出發(fā)，很容易得到一個(gè)圖結(jié)構(gòu)：每個(gè)原子事實(shí)對(duì)應(yīng)于圖中的一個(gè)節(jié)點(diǎn)。當(dāng)兩個(gè)節(jié)點(diǎn)所表示的原子事實(shí)出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中時(shí)，這兩個(gè)節(jié)點(diǎn)之間存在一條邊。所有出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中的原子事實(shí)組成了一個(gè)團(tuán)。

77馬爾可夫邏輯網(wǎng)從馬爾可夫邏輯網(wǎng)的定義出發(fā)，很容易得到一個(gè)圖結(jié)構(gòu)：每個(gè)原子事實(shí)對(duì)應(yīng)于圖中的一個(gè)節(jié)點(diǎn)。當(dāng)兩個(gè)節(jié)點(diǎn)所表示的原子事實(shí)出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中時(shí)，這兩個(gè)節(jié)點(diǎn)之間存在一條邊。所有出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中的原子事實(shí)組成了一個(gè)團(tuán)。

事實(shí)集合（世界空間）Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(A,B)Fr(B,A)Fr(B,B)78馬爾可夫邏輯網(wǎng)從馬爾可夫邏輯網(wǎng)的定義出發(fā)，很容易得到一個(gè)圖結(jié)構(gòu)：每個(gè)原子事實(shí)對(duì)應(yīng)于圖中的一個(gè)節(jié)點(diǎn)。當(dāng)兩個(gè)節(jié)點(diǎn)所表示的原子事實(shí)出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中時(shí)，這兩個(gè)節(jié)點(diǎn)之間存在一條邊。所有出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中的原子事實(shí)組成了一個(gè)團(tuán)。

事實(shí)集合（世界空間）Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(A,B)Fr(B,A)Fr(B,B)79馬爾可夫邏輯網(wǎng)從馬爾可夫邏輯網(wǎng)的定義出發(fā)，很容易得到一個(gè)圖結(jié)構(gòu)：每個(gè)原子事實(shí)對(duì)應(yīng)于圖中的一個(gè)節(jié)點(diǎn)。當(dāng)兩個(gè)節(jié)點(diǎn)所表示的原子事實(shí)出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中時(shí)，這兩個(gè)節(jié)點(diǎn)之間存在一條邊。所有出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中的原子事實(shí)組成了一個(gè)團(tuán)。

事實(shí)集合（世界空間）Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(A,B)Fr(B,A)Fr(B,B)80馬爾可夫邏輯網(wǎng)從馬爾可夫邏輯網(wǎng)的定義出發(fā)，很容易得到一個(gè)圖結(jié)構(gòu)：每個(gè)原子事實(shí)對(duì)應(yīng)于圖中的一個(gè)節(jié)點(diǎn)。當(dāng)兩個(gè)節(jié)點(diǎn)所表示的原子事實(shí)出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中時(shí)，這兩個(gè)節(jié)點(diǎn)之間存在一條邊。所有出現(xiàn)在同一個(gè)實(shí)例化規(guī)則之中的原子事實(shí)組成了一個(gè)團(tuán)。

命題集合（一個(gè)世界）81馬爾可夫邏輯網(wǎng)

Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(B,B)Fr(A,B)Fr(B,A)L1L2logit0000110000011100

00101100001111000100111101011111……………………………10101111221.5*2+1.1*211111111241.5*2+1.1*4

82馬爾可夫邏輯網(wǎng)研究任務(wù)利用馬爾可夫邏輯網(wǎng)對(duì)知識(shí)圖譜進(jìn)行建模后，我們可以：當(dāng)規(guī)則及其權(quán)重已知時(shí)：推斷知識(shí)圖譜中任意未知事實(shí)成立的概率（馬爾可夫隨機(jī)場(chǎng)的推斷問題）證據(jù)變量為知識(shí)圖譜中的已知事實(shí)，問題變量為未知事實(shí)當(dāng)規(guī)則已知但其權(quán)重未知時(shí)：自動(dòng)學(xué)習(xí)每條規(guī)則的權(quán)重（馬爾可夫隨機(jī)場(chǎng)的參數(shù)學(xué)習(xí)）當(dāng)規(guī)則及其權(quán)重均未知時(shí)：自動(dòng)學(xué)習(xí)規(guī)則及其權(quán)重（馬爾可夫隨機(jī)場(chǎng)的結(jié)構(gòu)學(xué)習(xí)），這實(shí)際上屬于我們討論過的歸納推理的范疇83擴(kuò)展閱讀84概率軟邏輯

85概率軟邏輯一階謂詞邏輯真值表松弛版本的邏輯聯(lián)結(jié)詞操作及不確定性規(guī)則建模1101111100100001110100010011成立當(dāng)且僅當(dāng)86概率軟邏輯概率軟邏輯建模示例不確定性規(guī)則不確定性事實(shí)規(guī)則實(shí)例建模87概率軟邏輯

88概率軟邏輯研究任務(wù)利用概率軟邏輯對(duì)知識(shí)圖譜進(jìn)行建模后，我們可以：當(dāng)規(guī)則及其權(quán)重已知時(shí)：推斷知識(shí)圖譜中任意未知事實(shí)成立的概率（馬爾可夫隨機(jī)場(chǎng)的推斷問題）證據(jù)變量為知識(shí)圖譜中的已知事實(shí)，問題變量為未知事實(shí)當(dāng)規(guī)則已知但其權(quán)重未知時(shí)：自動(dòng)學(xué)習(xí)每條規(guī)則的權(quán)重（馬爾可夫隨機(jī)場(chǎng)的參數(shù)學(xué)習(xí)）當(dāng)規(guī)則及其權(quán)重均未知時(shí)：自動(dòng)學(xué)習(xí)規(guī)則及其權(quán)重（馬爾可夫隨機(jī)場(chǎng)的結(jié)構(gòu)學(xué)習(xí)），這實(shí)際上屬于我們討論過的歸納推理的范疇89提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)90演繹推理：應(yīng)用推理規(guī)則91歸納推理：學(xué)習(xí)推理規(guī)則92推理規(guī)則

93推理規(guī)則概述

94提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)95歸納邏輯程序設(shè)計(jì)歸納邏輯程序設(shè)計(jì)（InductiveLogicProgramming,ILP）使用一階謂詞邏輯來進(jìn)行知識(shí)表示，通過修改和擴(kuò)充邏輯表達(dá)式來完成對(duì)數(shù)據(jù)的歸納。

背景知識(shí)樣例

96FOIL算法

97FOIL算法

從一般到特殊：逐步向規(guī)則體添加約束，直至其不覆蓋任何反例

98FOIL算法

99FOIL算法示例

背景知識(shí)樣例2.00-0.420.58-0.42NANANANANANA100FOIL算法示例

背景知識(shí)樣例2.00-0.420.58-0.42NANANANANANA

101FOIL算法示例

背景知識(shí)樣例-0.420.58-0.42NANANANANANA

102FOIL算法示例

背景知識(shí)樣例-0.420.58-0.42NANANANANANA

103傳統(tǒng)ILP問題VS知識(shí)圖譜傳統(tǒng)ILP問題：謂詞可以是多元的計(jì)算冗余且復(fù)雜度較高需要目標(biāo)謂詞的正例與反例封閉世界假設(shè)（ClosedWordAssumption）所有未聲明是正例的樣本全都是反例知識(shí)圖譜：謂詞幾乎都是二元的謂詞規(guī)模大、樣例數(shù)量多知識(shí)圖譜一般不顯式表示謂詞的反例開放世界假設(shè)（OpenWordAssumption）未聲明是正例的樣本既可以是反例，也可以是未知類別的樣本104擴(kuò)展閱讀：NeuralLogicMachinesNeuralLogicMachine(NLM),aneural-symbolicarchitectureforbothinductivelearningandlogicreasoning.

105提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)106知識(shí)圖譜中規(guī)則與關(guān)系路徑知識(shí)圖譜中包含的僅僅是實(shí)體間的二元關(guān)系，因此規(guī)則與知識(shí)圖譜中的關(guān)系路徑存在對(duì)應(yīng)關(guān)系。

107路徑排序算法PRA(PathRankingAlgorithm)[Laoetal.,2011]

以實(shí)體間的路徑作為特征，來學(xué)習(xí)目標(biāo)關(guān)系的分類器。

RandomWalkInferenceandLearningina

largescaleKnowledgeBase,EMNLP2011.108路徑排序算法PRA工作流程特征抽?。荷刹⑦x擇路徑特征集合特征計(jì)算：計(jì)算每個(gè)訓(xùn)練樣例的特征值分類器訓(xùn)練：根據(jù)訓(xùn)練樣例，為每個(gè)目標(biāo)關(guān)系訓(xùn)練一個(gè)分類器TomLyonBobFRParisLivedInCityNationalityCityLocatedInCountryBornInCityClassMatesCityLocatedInCountryBornInCity109路徑排序算法PRA工作流程特征抽?。弘S機(jī)游走，廣度優(yōu)先搜索，深度優(yōu)先搜索特征計(jì)算：隨機(jī)游走概率，布爾值（出現(xiàn)/不出現(xiàn)），出現(xiàn)頻次/頻率分類器訓(xùn)練：?jiǎn)稳蝿?wù)學(xué)習(xí)：為每個(gè)關(guān)系單獨(dú)訓(xùn)練一個(gè)二分類分類器多任務(wù)學(xué)習(xí)：將不同關(guān)系進(jìn)行聯(lián)合學(xué)習(xí)，同時(shí)訓(xùn)練它們的分類器110路徑排序算法PRA規(guī)則學(xué)習(xí)：根據(jù)分類器權(quán)重自動(dòng)挖掘并篩選可靠規(guī)則PRA在Freebase上挖掘出的規(guī)則111PRA挖掘路徑和規(guī)則112PRA進(jìn)行關(guān)系推理實(shí)驗(yàn)效果113提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)114規(guī)則學(xué)習(xí)評(píng)估方法

115AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘AMIE

(AssociationRuleMiningunderIncompleteEvidence)[Galárragaetal.,2013]

支持從不完備的知識(shí)庫中，挖掘閉式（closed）規(guī)則。兩個(gè)謂詞共享一個(gè)變量或?qū)嶓w，則稱其為連通的。規(guī)則中任意兩個(gè)謂詞可通過連通關(guān)系的傳遞性相連，則稱該規(guī)則為連通的。規(guī)則是連通的并且其中的變量都至少出現(xiàn)兩次，則稱其為閉式（closed）邏輯規(guī)則。116AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘AMIE依次學(xué)習(xí)預(yù)測(cè)每種關(guān)系的規(guī)則。對(duì)于每種關(guān)系，從規(guī)則體為空的規(guī)則開始，通過三種操作擴(kuò)展規(guī)則體部分，保留支持度大于閾值的候選（閉式）規(guī)則。添加懸掛邊(AddDanglingAtom)：懸掛邊是指邊的一端是一個(gè)未出現(xiàn)過的變量，而另一端（變量或常量）是在規(guī)則中出現(xiàn)過的。添加實(shí)例邊(AddInstantiatedAtom)：實(shí)例邊與懸掛邊類似，邊的一端也是在規(guī)則中出現(xiàn)過的變量或常量，但另一端是未出現(xiàn)過的常量，也就是知識(shí)庫中的實(shí)體。添加閉合邊(AddClosingAtom)：閉合邊則是連接兩個(gè)已經(jīng)存在于規(guī)則中的元素（變量或常量）的邊。117AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘AMIE工作流程示意

118AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘AMIE規(guī)則評(píng)估支持度(support)：同時(shí)符合規(guī)則體和規(guī)則頭的實(shí)例數(shù)目置信度(confidence)：支持度除以僅符合規(guī)則體的實(shí)例數(shù)目119AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘AMIE規(guī)則評(píng)估支持度(support)：同時(shí)符合規(guī)則體和規(guī)則頭的實(shí)例數(shù)目置信度(confidence)：支持度除以僅符合規(guī)則體的實(shí)例數(shù)目封閉世界假設(shè)(ClosedWorldAssumption)：知識(shí)庫中不存在的事實(shí)都是錯(cuò)誤的120AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘

/~weblt/pikm2014/slides/Luis-Galarraga-applications-rule-mining.pdf121AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘

應(yīng)該算反例不應(yīng)該算反例122AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘AMIE規(guī)則評(píng)估支持度(support)：同時(shí)符合規(guī)則體和規(guī)則頭的實(shí)例數(shù)目置信度(confidence)：支持度除以僅符合規(guī)則體的實(shí)例數(shù)目PCA置信度(PCAconfidence)：123AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘只要存在一個(gè)不是y的才可算數(shù)124AMIE：不完備知識(shí)庫中的關(guān)聯(lián)規(guī)則挖掘AMIE在YAGO上挖掘出的規(guī)則http://resources.mpi-inf.mpg.de/yago-naga/amie/data/yago2/amie_yago2_2.html125相關(guān)工作：基于表示學(xué)習(xí)獲取推理規(guī)則

Embeddingentitiesandrelationsforlearningandinferenceinknowledgebases,ICLR2015.126提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)127知識(shí)圖譜的數(shù)值表示（向量化表示）把知識(shí)庫中的實(shí)體和關(guān)系表示為低維空間的對(duì)象（向量）及其它們的操作（空間轉(zhuǎn)換）；該表示能夠蘊(yùn)涵其在知識(shí)庫中的性質(zhì)，即具有類似上下文的對(duì)象，在低維空間中更接近。第j

個(gè)實(shí)體第i

個(gè)實(shí)體第k

個(gè)關(guān)系事實(shí)集合

學(xué)習(xí)實(shí)體和關(guān)系的低維表示

事實(shí)推理表示學(xué)習(xí)技術(shù)：從原始數(shù)據(jù)中學(xué)習(xí)概念的潛在表示128分布式知識(shí)表示分布式知識(shí)表示（KnowledgeGraphEmbedding）的核心思想是將符號(hào)化的實(shí)體和關(guān)系在低維連續(xù)向量空間進(jìn)行表示，在簡(jiǎn)化計(jì)算的同時(shí)最大程度保留原始的圖結(jié)構(gòu)?；静襟E：實(shí)體關(guān)系表示：定義實(shí)體和關(guān)系在向量空間中的表示形式（向量/矩陣/張量）。打分函數(shù)定義：定義打分函數(shù)，衡量每個(gè)三元組成立的可能性。表示學(xué)習(xí)：構(gòu)造優(yōu)化問題，學(xué)習(xí)實(shí)體和關(guān)系的低維連續(xù)向量表示。129位移距離模型代表性方法：TransE及其變種目標(biāo)：頭尾實(shí)體表示之差與關(guān)系表示一致headentity+relation=tailentityChina–Beijing=France–Paris=capital-ofBeijing+capital-of=ChinaParis+capital-of=France130語義匹配模型代表性方法：RESCAL及其變種直接根據(jù)三元組頭尾實(shí)體和關(guān)系的表示定義計(jì)算函數(shù)matching(relation,composition(head,tail))頭尾實(shí)體和關(guān)系都為向量逐位相乘并累加得到事實(shí)打分頭尾實(shí)體和關(guān)系都為向量間隔位置相乘并累加得到事實(shí)打分頭尾實(shí)體為向量，關(guān)系為矩陣頭實(shí)體與矩陣相乘然后與尾實(shí)體計(jì)算內(nèi)積得到事實(shí)打分131融合多元化信息的分布式知識(shí)表示上述分布式知識(shí)表示方法僅用到了知識(shí)圖譜中的三元組信息，還有多種其他類型的信息也被證實(shí)能夠提升分布式知識(shí)表示的效果。實(shí)體類別關(guān)系路徑實(shí)體描述文本邏輯規(guī)則…/xinguoxia/KGE132提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)133DeepPath：基于強(qiáng)化學(xué)習(xí)的推理PRA算法的升級(jí)版，利用強(qiáng)化學(xué)習(xí)（RL）學(xué)習(xí)路徑（paths）將知識(shí)圖譜推理簡(jiǎn)化為一個(gè)“事實(shí)判斷”（FactPrediction）事實(shí)判斷即確定一個(gè)三元組（h,r,t）是否成立尋找一條能鏈接已知頭實(shí)體h和尾實(shí)體的路徑，并將此問題建模為序列決策問題。訓(xùn)練基于策略梯度的強(qiáng)化學(xué)習(xí)方法搜索路徑。需要事先編碼KG，使用TransE等傳統(tǒng)方法預(yù)訓(xùn)練KGDeepPath:AReinforcementLearningMethodforKnowledgeGraphReasoning,EMNLP2017.134DeepPath模型示意圖

135DeepPath效果：關(guān)系預(yù)測(cè)對(duì)于每個(gè)三元組，使用PRA得到TopK結(jié)果，來得到訓(xùn)練和測(cè)試樣本的負(fù)樣本（即替換掉真實(shí)三元組中的t為t’）。判斷真實(shí)的(h,r,t)是否得分最高136DeepPath學(xué)習(xí)得到的路徑樣例137基于強(qiáng)化學(xué)習(xí)的查詢問答把知識(shí)推理定義為查詢問題任務(wù)<ColinKaepernick,PlaysInLeague,?>無法“預(yù)知”答案對(duì)應(yīng)的尾實(shí)體（更符合真實(shí)場(chǎng)景）需要盡可能避免遍歷大規(guī)模知識(shí)圖譜（影響算法效率）GoforaWalkandArriveattheAnswer:ReasoningOverPathsinKnowledgeBasesusingReinforcementLearning,ICLR2018.138MINERVA模型

139MINERVA模型

140MINERVA模型的實(shí)驗(yàn)結(jié)果事實(shí)預(yù)測(cè)效果（與DeepPath的比較）鏈接預(yù)測(cè)（無性能優(yōu)勢(shì)）141提綱知識(shí)推理概述什么是推理推理方式及分類知識(shí)推理典型應(yīng)用演繹推理：推理具體事實(shí)經(jīng)典邏輯推理基于產(chǎn)生式規(guī)則的推理基于概率邏輯學(xué)習(xí)的推理歸納推理：學(xué)習(xí)推理規(guī)則歸納推理概述歸納邏輯程序設(shè)計(jì)路徑排序算法（PRA算法）關(guān)聯(lián)規(guī)則挖掘算法（AMIE算法）知識(shí)圖譜推理新進(jìn)展基于表示學(xué)習(xí)的知識(shí)圖譜推理基于強(qiáng)化學(xué)習(xí)的知識(shí)圖譜推理符號(hào)規(guī)則與表示學(xué)習(xí)相融合的知識(shí)圖譜推理總結(jié)142推理模式人類進(jìn)行推理時(shí)，往往呈現(xiàn)出以下兩個(gè)特點(diǎn)：考慮盡可能多的因素，全局推理。實(shí)際中，考慮的影響因素越全面，就越有可能得到正確的推理結(jié)論。人的智能表現(xiàn)在可以利用潛在的推理模式，而這些推理模式難以窮舉。有些事物之間雖然沒有呈現(xiàn)出顯式的聯(lián)系，但有可能存在尚未探知的隱式規(guī)律。143符號(hào)推理VS.數(shù)值推理之前介紹的幾種歸納和演繹推理方法都屬于符號(hào)推理的范疇，即在知識(shí)圖譜中的實(shí)體和關(guān)系符號(hào)上直接進(jìn)行推理。與符號(hào)推理相對(duì)的就是數(shù)值推理，即使用數(shù)值計(jì)算，尤其是向量矩陣計(jì)算的方法，捕捉知識(shí)圖譜上隱式的關(guān)聯(lián)，模擬推理的進(jìn)行?；诜植际街R(shí)表示的推理就是典型的數(shù)值推理方法。捕捉實(shí)體和關(guān)系之間的隱式關(guān)聯(lián)分布式空間映射對(duì)特征間的復(fù)雜關(guān)系進(jìn)行了解耦，減少了維數(shù)災(zāi)難問題（curseofdimensionality）使符號(hào)數(shù)據(jù)可以直接參與運(yùn)算且計(jì)算速度非常快144符號(hào)推理與分布式表示推理的比較符號(hào)表示分布式表示表示方法離散符號(hào)連續(xù)的數(shù)值推理范圍局部全局推理的精確性高較低效率小規(guī)模高，大規(guī)模低高是否易被人理解容易困難與其他系統(tǒng)結(jié)合的難易程度難易跨領(lǐng)域難（需專家設(shè)計(jì)種子規(guī)則）易知識(shí)推理：融合之道融合符號(hào)表示和分布式表示的知識(shí)推理145SystemIvs.SystemIIReasoningSystemI感知能力，如識(shí)別圖像中的對(duì)象等高效推理（Fast）例如，KnowledgeGraphEmbedding（得到分布式向量表示）SystemII認(rèn)知能力，涉及邏輯推理和規(guī)劃嚴(yán)謹(jǐn)推理（Slow）例如，MarkovLogicNetwork（根據(jù)周圍事實(shí)的標(biāo)簽進(jìn)行邏輯推理）146IterE模型知識(shí)圖譜

挖掘規(guī)則

推理事實(shí)

補(bǔ)充知識(shí)圖譜知識(shí)圖譜

表示學(xué)習(xí)

規(guī)則約束

推理知識(shí)AxiomInduction（計(jì)算規(guī)則權(quán)重）IterativelyLearningEmbeddingsandRulesforKnowledgeGraphReasoning,WWW2019.147IterE模型148SoLE模型規(guī)則實(shí)例化將規(guī)則中變量替換成知識(shí)實(shí)例后的結(jié)果對(duì)（實(shí)例化的）規(guī)則進(jìn)行數(shù)值約束EnhancedKnowledgeGraphEmbeddingbyJointlyLearningSoftRulesandFacts,Algorithms2019.149SoLE模型簡(jiǎn)單事實(shí)建模：輸入事實(shí)得到概率得分（0-1）組合知識(shí)建模：與、或、非、蘊(yùn)含基于規(guī)則的約束EnhancedKnowledgeGraphEmbeddingbyJointlyLearningSoftRulesandFacts,Algorithms2019.規(guī)則的fp置信度150推理規(guī)則與表示學(xué)習(xí)相融合IterE模型優(yōu)點(diǎn)：可以迭代地學(xué)習(xí)規(guī)則置信度和推理缺點(diǎn)：需要人工定義公理模板，直接加入的事實(shí)包含大量的噪聲SoLE模型優(yōu)點(diǎn)：利用AMIE挖掘的高質(zhì)量規(guī)則缺點(diǎn)：缺乏持續(xù)學(xué)習(xí)的能力，同樣規(guī)則推理會(huì)引入部分噪聲，規(guī)則實(shí)例數(shù)量組合爆炸151神經(jīng)符號(hào)邏輯推理馬爾可夫邏輯網(wǎng)結(jié)合一階邏輯和概率圖模型

152馬爾可夫邏輯網(wǎng)

表示學(xué)習(xí)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：可以通過隨機(jī)梯度下降高效訓(xùn)練鏈接預(yù)測(cè)高召回率缺點(diǎn)：難以利用領(lǐng)域知識(shí)（邏輯規(guī)則）153pLogicNet模型將馬爾可夫邏輯網(wǎng)絡(luò)和表示學(xué)習(xí)結(jié)合起來用馬爾可夫邏輯網(wǎng)絡(luò)定義事實(shí)的聯(lián)合分布使用變分EM