人工智能大學(xué)課件

2.3謂詞邏輯法一.謂詞邏輯的簡要回顧

1.命題與謂詞命題:表示客觀事實的語句李明是個工人 LIWORKER或L把謂語部分提出WORKER(LI)WORKER(WANG)引入變量、函數(shù)和量詞(x)(HUMAN(x)->NEED-STUDY(x))(x)TEACHER(brother(x))注:我們只討論一階謂詞演算.2.3謂詞邏輯法一.謂詞邏輯的簡要回顧12.合適公式(well-formedformula)原子(謂詞)公式原子公式::=謂詞名+“(”+項[,項]+“)”項::=常量|變量|函數(shù)函數(shù)::=函數(shù)名+“(”+參數(shù)[,參數(shù)]+“)”合適公式原子謂詞公式是合適公式;若A是合適公式,則~A也是合適公式;若A和B都是合適公式,則AB,AVB,AB也都是合適公式;若A是合適公式,x為任何變量,則(x)A和(x)A也是合適公式;只有按上述規(guī)則產(chǎn)生的公式才是合適公式.(有限步)2.合適公式(well-formedformula)2

3.用謂詞公式表達知識

例:任何整數(shù)或者是正數(shù)或者是負數(shù).用I(x)表示“x是整數(shù)”,用P(x)表示“x是正數(shù)”,用N(x)表示“x是負數(shù)”.

(x)(I(x)(P(x)VN(x)))

例:用謂詞邏輯表達積木世界.3.用謂詞公式表達知識3一.基本概念

語義網(wǎng)絡(luò)是一種用實體及其語義關(guān)系來表達知識的有向圖.結(jié)點:代表實體,表示各種事物、概念、情況、屬性、狀態(tài)、事件、動作等;

弧:代表語義關(guān)系,表示它所連接的兩個實體之間的語義聯(lián)系.

在語義網(wǎng)絡(luò)中,每一個結(jié)點和弧都必須帶有標識,這些標識用來說明它所代表的實體或語義.二.以個體為中心的語義網(wǎng)絡(luò)1.實例聯(lián)系

2.4語義網(wǎng)絡(luò)法一.基本概念2.4語義網(wǎng)絡(luò)法4

2.泛化聯(lián)系

3.聚集聯(lián)系2.泛化聯(lián)系5

4.屬性聯(lián)系三.以謂詞為中心的語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)表示法和謂詞邏輯表示法之間有著對應(yīng)的表示能力.

1.二元謂詞4.屬性聯(lián)系6

2.n元謂詞n元謂詞可轉(zhuǎn)化為n個二元謂詞的合取例:“李明給王宏<<圍城>>”3.連接詞的表達例:“李明給王宏<<圍城>>而且王宏讀了<<圍城>>”2.n元謂詞7

4.量詞的表達存在量詞的表達,例:“某個大學(xué)生讀過<<圍城>>”

人工智能大學(xué)課件8全稱量詞的表達,采用語義網(wǎng)絡(luò)分塊化技術(shù).例:“所有的大學(xué)生都讀過<<圍城>>”人工智能大學(xué)課件9三.語義網(wǎng)絡(luò)的推理1.網(wǎng)絡(luò)匹配2.繼承推理3.網(wǎng)絡(luò)演繹四.語義網(wǎng)絡(luò)的特點1.優(yōu)點

結(jié)構(gòu)性,聯(lián)想性,自索引性,自然性2.缺點推理規(guī)則不十分明了表達范圍有限，一旦結(jié)點個數(shù)太多，網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，推理就難以進行

三.語義網(wǎng)絡(luò)的推理102.5框架表示一.框架是一種結(jié)構(gòu)性的知識表達方法框架的作用:表示事物各方面的屬性表示事物之間的類屬關(guān)系事物的特征和變異識別、分析、預(yù)測事物及其行為一.框架的基本結(jié)構(gòu)例:有下列描述“2000年5月13日,在西藏的阿里地區(qū)發(fā)生了里氏5.3級地震,傷亡24人,死亡1人,財產(chǎn)損失2000萬人民幣”把他表示為框架如下:Frame(框架名):地震Slot1(槽名):時間:2000年5月13日Slot2(槽名):地點:西藏的阿里地區(qū)2.5框架表示一.框架是一種結(jié)構(gòu)性的知識表達方法11

Slot3(槽名):震級:里氏5.3級Slot4(槽名):傷亡人數(shù):24Slot5(槽名):死亡人數(shù):1Slot6(槽名):財產(chǎn)損失:2000萬人民幣框架的一般結(jié)構(gòu)<框架名><槽1><側(cè)面11><值111><值112>...<側(cè)面12><值121><值122>......<槽2><側(cè)面21><值211><值212>.........<槽n><側(cè)面n1><值n11>......有兩種特殊的側(cè)面:默認值側(cè)面,附加過程側(cè)面Slot3(槽名):震級:里氏5.3級12三.框架的推理1.匹配,是不完全匹配2.繼承推理3.填槽四.附加過程側(cè)面的類型1.if-needed2.if-added3.if-removed三.框架的推理133456789101112131415161718192021★2324★26272829303112活結(jié)點表1121124224844816881616817881717884944918991818919919194425225105510209991010202010211010212110105115511★深度優(yōu)先搜索示意圖3456789101112131415161718192021412345678910111213141516171819★21222324★26272829303112345678910111213141516171819★活結(jié)點表234567891011121314151617181912345678910123456789寬度優(yōu)先搜索演示圖12345678910111213141516171819★15寬度優(yōu)先2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652567312384765目標8234187654寬度優(yōu)先23232816深度優(yōu)先231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目標深度優(yōu)先232328173.2啟發(fā)式搜索一.基本思想也叫LC-搜索（按成本最小的原則從活結(jié)點表中作選擇）需要定義一個評價函數(shù)c，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展.二.評價函數(shù) f(n)=h(n)+g(n)

f(n):評價函數(shù)或叫作成本函數(shù),表示從開始到目前,再到找到一個問題解的所花費的最小成本的估計.g(n):表示從開始到目前所花費的成本值或其估計.h(n):啟發(fā)函數(shù),表示從目前到找到一個問題的最小成本的一個估計.3.2啟發(fā)式搜索一.基本思想18345678910111213141516171819★21222324★26272829303112活結(jié)點表112233244554889951010111110★1245LC-搜索示意圖345678910111213141516171819★2119三.舉例:九宮重排83647■5初始狀態(tài)1238■4765目標狀態(tài)h(X)：結(jié)點X的格局與目標格局相比，位置不符合的將牌數(shù)目；三.舉例:九宮重排83初始狀態(tài)123202831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■65■2318476523■184765123■847651238■4765123784■650+41+51+31+52+32+32+43+3

3+43+2

3+44+15+05+2目標2832832214.3人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)一.人工神經(jīng)網(wǎng)絡(luò)的基本要素:.神經(jīng)單元.輸入與輸出.輸出函數(shù).激勵函數(shù).連接模式.傳播規(guī)則.學(xué)習(xí)法則4.3人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)一.人工神經(jīng)網(wǎng)絡(luò)的基本要素:22二.人工神經(jīng)網(wǎng)絡(luò)模型

二.人工神經(jīng)網(wǎng)絡(luò)模型23三.人工神經(jīng)網(wǎng)絡(luò)各部分特性1.神經(jīng)單元

分為輸入單元,輸出單元和隱單元每個單元有激活值,可以是連續(xù)實數(shù)值,也可以是離散整數(shù)值2.輸入與輸出

從網(wǎng)絡(luò)外部到網(wǎng)絡(luò)內(nèi)部的為輸入信號從網(wǎng)絡(luò)內(nèi)部到網(wǎng)絡(luò)外部的為輸出信號三.人工神經(jīng)網(wǎng)絡(luò)各部分特性243.輸出函數(shù)

單元的輸出信號與單元激活值的映射關(guān)系可以是等值函數(shù),也可以是閾值函數(shù)4.激勵函數(shù)單元的總輸入信號與單元激活值的映射關(guān)系可以是等值函數(shù),也可以是閾值函數(shù)或可微的連續(xù)函數(shù)3.輸出函數(shù)255.連接模式

網(wǎng)絡(luò)中所有單元連接強度(權(quán)值)構(gòu)成的矩陣6.傳播規(guī)則

某個神經(jīng)單元所接受的總輸入與其它單元對該單元輸出之間的關(guān)系,最常用的為加權(quán)傳播法則.5.連接模式267.學(xué)習(xí)法則神經(jīng)網(wǎng)絡(luò)的運行包括兩個階段：1.訓(xùn)練或?qū)W習(xí)階段向神經(jīng)網(wǎng)絡(luò)提供一系列輸入－輸出數(shù)據(jù)組,通過數(shù)值計算方法和參數(shù)優(yōu)化技術(shù),使節(jié)點連接的權(quán)值不斷調(diào)整,直到從給定的輸入能產(chǎn)生所期望的輸出.22.預(yù)測（應(yīng)用）階段以訓(xùn)練好的網(wǎng)絡(luò),對未知的樣本進行預(yù)測

人工神經(jīng)網(wǎng)絡(luò)的主要學(xué)習(xí)算法.有師學(xué)習(xí).無師學(xué)習(xí).強化學(xué)習(xí)7.學(xué)習(xí)法則274.4線性模型與感知機一.線性網(wǎng)絡(luò)模型特征

1.只有輸入單元和輸出單元,沒有隱單元2.單元激活值為連續(xù)實數(shù)值3.輸出函數(shù)和激活函數(shù)均為等值函數(shù)4.采用加權(quán)傳播規(guī)則線性網(wǎng)絡(luò)模型等價于線形方程組(請課后自行分析)多層線性模型可以找到等價的雙層線形模型(既隱單元對線形模型是多余的)請在作業(yè)中證明.4.4線性模型與感知機一.線性網(wǎng)絡(luò)模型特征28二.線性閾值模型的特征

1.既有輸入單元和輸出單元,也有隱單元2.單元激活值為{0,1}3.輸出函數(shù)為等值函數(shù)4.激活函數(shù)為閾值函數(shù)5.采用加權(quán)傳播規(guī)則二.線性閾值模型的特征29三.兩層線性閾值模型(感知機)這是一個表達或邏輯的模型它可以用delta學(xué)習(xí)法則學(xué)習(xí)

三.兩層線性閾值模型(感知機)30感知機無法表達異或邏輯(請在課后作業(yè)證明)異或邏輯甚至更復(fù)雜的布爾代數(shù)只能用多層線形閾值模型表達,但無法找到合適的學(xué)習(xí)法則.感知機局限性的分析:感知機無法表達異或邏輯(請在課后作業(yè)證明)314.5BP模型及應(yīng)用一.BP模型(反向傳播網(wǎng)絡(luò))的特征

1.既有輸入單元和輸出單元,也有隱單元2.單元激活值為連續(xù)實數(shù)值3.輸出函數(shù)為等值函數(shù)4.激活函數(shù)為非遞減的可微函數(shù)例如Sigmoid函數(shù),非對稱Sigmoid函數(shù)為f(X)=1/(1+e-x),對稱Sigmoid函數(shù)f(X)=(1-e-x)/(1+e-x).5.采用加權(quán)傳播規(guī)則6.學(xué)習(xí)算法采用的是梯度下降法，它使期望輸出與實際輸出之間的誤差平方和最小.4.5BP模型及應(yīng)用一.BP模型(反向傳播網(wǎng)絡(luò))的特征32設(shè)誤差e采用下式表示：

其中,Yi＝f〔W*·Xi]是對應(yīng)第i個樣本Xi的實時輸出Yi是對應(yīng)第i個樣本Xi的期望輸出.要使誤差e最小，可先求取e的梯度：設(shè)誤差e采用下式表示：33二.BP模型的應(yīng)用范圍及局限.BP模型廣泛應(yīng)用于模式識別,預(yù)測,信號處理等領(lǐng)域.經(jīng)數(shù)學(xué)證明,它可以表達任意連續(xù)函數(shù).其缺點是學(xué)習(xí)時間長,收斂慢,且容易陷入局部最小,原因是誤差曲面復(fù)雜.二.BP模型的應(yīng)用范圍及局限34三.BP模型的應(yīng)用舉例

實例：應(yīng)用BP網(wǎng)絡(luò)預(yù)測氣候變化對雅礱江流域徑流的影響.經(jīng)分析,在諸多氣候因子中,流域內(nèi)年均氣溫和年均降水量是影響流域年均徑流的兩個主要因子,若把氣溫和降水看作輸入,徑流看作輸出,可用BP網(wǎng)絡(luò)來研究氣溫和降水變化對流域徑流的影響.建立三層BP網(wǎng)絡(luò)(輸入層、輸出層和一個隱蔽層),以年均氣溫和年均降水量作為BP網(wǎng)絡(luò)輸入層的輸入單元,年均徑流量為網(wǎng)絡(luò)輸出層的輸出單元.用1960到1990年共31年實測的年均氣溫、降水和徑流量系列資料(即31個樣本對)對網(wǎng)絡(luò)進行訓(xùn)練、檢驗,其中1960—1982年資料作為訓(xùn)練樣本，1983-1990年資料作為檢驗樣本。三.BP模型的應(yīng)用舉例35BP網(wǎng)絡(luò)在雅礱江流域年均流量的擬合與預(yù)測精度(%)

項目BP網(wǎng)絡(luò)模型線性回歸模型備注平均相對誤差5.996.65擬合最大相對誤差17.0018.52平均相對誤差7.819.33預(yù)測最大相對誤差21.0325.46

摘自<<水利學(xué)報>>99年第1期BP網(wǎng)絡(luò)在雅礱江流域年均流量的擬合與預(yù)測精度(%)365.1遺傳算法一.概述

1.遺傳算法(GeneticAlgorithms,簡稱GA)思想來源于生物進化過程,它是基于進化過程中的信息遺傳機制和優(yōu)勝劣汰的自然選擇原則的搜索算法(以字符串表示狀態(tài)空間).

2.GA由美國J.H.Holland教授于1975年首先提出,并以其提出的圖式定理作為理論基礎(chǔ).

12/11/20225.1遺傳算法一.概述12/10/2022373.GA特別適用于傳統(tǒng)數(shù)學(xué)難以解決的復(fù)雜的優(yōu)化問題,如TSP問題.

4.GA屬于鄰域搜索的一類,它用概率方式產(chǎn)生新的鄰域個體.

5.簡單的GA存在參數(shù)難以控制,容易陷入局部收斂等缺陷,現(xiàn)在的趨勢是把它與其他的優(yōu)化算法結(jié)合起來取長補短.3.GA特別適用于傳統(tǒng)數(shù)學(xué)難以解決的復(fù)雜的優(yōu)化問題,如TS38二.遺傳算法的基本機理

1.編碼與解碼遺傳算法先將搜索結(jié)構(gòu)編碼為字符串形式,每個字符串結(jié)構(gòu)被稱為個體(染色體).相反將字符串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫解碼.編碼方法有二進制編碼,實數(shù)編碼,符號編碼等.

二.遺傳算法的基本機理39

2.染色體優(yōu)劣的度量----適應(yīng)度每個染色體與其適應(yīng)度的對應(yīng)關(guān)系是適應(yīng)度函數(shù),它應(yīng)該有效反映每個染色體與問題的最優(yōu)解染色體之間的差距.3.遺傳操作

選擇(復(fù)制),根據(jù)個體的適應(yīng)度函數(shù)值決定它在下一代被淘汰還是被遺傳.

交叉將被選擇的兩個個體作為母體進行部分子串的交換.2.染色體優(yōu)劣的度量----適應(yīng)度40

變異就是改變?nèi)旧w的某些基因.三.遺傳算法的準備工作

1.確定表示方案;2.確定適應(yīng)值的度量;3.確定控制該算法的參數(shù)和變量;4.確定怎樣指定結(jié)果及程序運行結(jié)束的標準.人工智能大學(xué)課件41四.遺傳算法的具體步驟1.隨機產(chǎn)生一個由固定長度字符串組成的初始群體;2.對于字符串群體,迭代地執(zhí)行下述步驟,直到選種標準被滿足為止:計算群體中的每個個體字符串的適應(yīng)值;應(yīng)用下述三種操作(至少前兩種)來產(chǎn)生新的群體:復(fù)制:把現(xiàn)有的個體字符串復(fù)制到新的群體中.雜交:通過遺傳重組隨機選擇兩個現(xiàn)有的子字符串,產(chǎn)生新的字符串.變異:將現(xiàn)有字符串中某一位的字符隨機變異.人工智能大學(xué)課件42

3.把在后代中出現(xiàn)的最高適應(yīng)值的個體字符串指定為遺傳算法運行的結(jié)果.這一結(jié)果可以是問題的解(或近似)4.簡單的雜交操作分為三步從當前群體B(t)中選擇兩個結(jié)構(gòu)：

隨機選擇一個整數(shù)交換a和a‘中位置x左邊的元素,產(chǎn)生兩個新的結(jié)構(gòu)：3.把在后代中出現(xiàn)的最高適應(yīng)值的個體字符串指定為遺傳算435.簡單的變異操作過程如下:每個位置的字符變量都有一個變異概率,各位置互相獨立.通過隨機過程選擇發(fā)生變異的位置：產(chǎn)生一個新結(jié)構(gòu)其中是從對應(yīng)位置的字符變量的值域中隨機選擇的一個取值?？梢酝瑯拥玫?.簡單的變異操作過程如下:44GEN=0概率地選擇遺傳操作隨機創(chuàng)建初始群體是否滿足選中標準？計算群體中每個個體的適應(yīng)值i:=0i:=M指定結(jié)果結(jié)束GEN:=GEN+1是是否GEN=0概率地選擇遺傳操作隨機創(chuàng)建初始群體是否滿足選中標準45概率地選擇遺傳操作根據(jù)適應(yīng)值選擇一個個體完成雜交i:=i+1i:=i+1完成繁殖p(r)繁殖基于適應(yīng)值選擇兩個個體把新的兩個孩子加到群體中p(c)雜交變異p(m)把新的孩子加入到群體中完成變異根據(jù)適應(yīng)值選擇一個個體把變異后個體加入到群體中概率地選擇遺傳操作根據(jù)適應(yīng)值選完成雜交i:=i+1i:=i+46五.遺傳算法與傳統(tǒng)優(yōu)化算法的主要不同遺傳算法不是直接作用在參變量集上,而是利用參變量集的某種編碼;遺傳算法不是從單個點,而是在群體中從一個點開始搜索;遺傳算法利用適應(yīng)值信息,無需導(dǎo)數(shù)或其它輔助信息;遺傳算法利用概率轉(zhuǎn)移規(guī)則,而非確定性規(guī)則.五.遺傳算法與傳統(tǒng)優(yōu)化算法的主要不同47六.遺傳算法舉例問題：求（1）編碼：此時取均長為5，每個染色體（2）初始群體生成：群體大小視情況而定，此處設(shè)置為4，隨機產(chǎn)生四個個體：編碼：01101，11000，01000，10011解碼：1324819適應(yīng)度：16957664361（3）適應(yīng)度評價：六.遺傳算法舉例484）選擇：選擇概率個體：01101，11000，01000，10011適應(yīng)度：16957664361選擇概率：0.140.490.060.31選擇結(jié)果：01101，11000，11000，10011（5）交叉操作：發(fā)生交叉的概率較大哪兩個個體配對交叉是隨機的交叉點位置的選取是隨機的（單點交叉）01101011001100011011110001100110011100004）選擇：選擇概率49（6）變異：發(fā)生變異的概率很?。?）新群體的產(chǎn)生：保留上一代最優(yōu)個體，一般為10%左右，至少1個用新個體取代舊個體，隨機取代或擇優(yōu)取代。11000，11011，11001，10011（8）重復(fù)上述操作：說明：GA的終止條件一般人為設(shè)置；GA只能求次優(yōu)解或滿意解。分析：按第二代新群體進行遺傳操作，若無變異，永遠也找不到最優(yōu)解——擇優(yōu)取代有問題。若隨機的將個體01101選入新群體中，有可能找到最優(yōu)解。（6）變異：發(fā)生變異的概率很小50七.遺傳算法應(yīng)用中的一些基本問題1.編碼二進制編碼,十進制編碼適用于函數(shù)優(yōu)化二進制編碼需要解碼,染色體較長,變異容易.十進制編碼直觀,交換計算量小,但變異復(fù)雜.符號編碼適用于組合優(yōu)化

2.適應(yīng)度函數(shù)適應(yīng)度函數(shù)要求非負,同時把待解優(yōu)化問題表達為最大化問題,不同染色體的適應(yīng)度值既要有差距,又不要差距過大.

七.遺傳算法應(yīng)用中的一些基本問題51

為此,需要對原始函數(shù)進行某些數(shù)學(xué)變換.如:非負變換,線性變換,冪變換,指數(shù)變換等.3.控制參數(shù)和終止條件(1)需要控制的參數(shù)有種群大小,交叉概率和變異概率.它們的設(shè)定尚無理論指導(dǎo),根據(jù)具體問題和實驗確定.變異概率的選擇尤為困難.(2)簡單的GA不能收斂到全局最優(yōu)解,通過改進才行,但搜索時間可能很長.

為此,需要對原始函數(shù)進行某些數(shù)學(xué)變換.如:非負52

(3)沒有嚴格的數(shù)學(xué)方法判定算法的終止.大多數(shù)采用啟發(fā)式方法.八.簡單遺傳算法的改進1.改進選擇方法例如:擇優(yōu)選擇法,確定選擇法等2.增加遺傳操作例如:多點交叉,部分匹配交叉,基因重組等3.單親遺傳取消交叉操作4.混合遺傳算法

(3)沒有嚴格的數(shù)學(xué)方法判定算法的終止.大多535.2進化策略一.進化策略的算法模型進化策略模仿自然進化原理作為一種求解參數(shù)優(yōu)化問題的方法.最簡單的實現(xiàn)方法如下:定義的問題是尋找n維的實數(shù)向量x,它使函數(shù)(2)雙親向量的初始群體從每維可行范圍內(nèi)隨機選擇.(3)子孫向量的創(chuàng)建是從每個雙親向量加上零均方差高斯隨機變量.(4)根據(jù)最小誤差選擇向量為下一代新的雙親.(5)向量的標準偏差保持不變,或者沒有可用的計算方法,那么處理結(jié)束.5.2進化策略一.進化策略的算法模型54二.進化策略的具體步驟:1.產(chǎn)生出初始群體,它由關(guān)于問題(計算機程序)的函數(shù)隨機組合而成。2.迭代完成下述子步驟，直至滿足選種標準為止:執(zhí)行群體中的每個程序，根據(jù)它解決問題的能力，給它指定一個適應(yīng)值應(yīng)用變異等操作創(chuàng)造新的計算機程序群體?；谶m應(yīng)值根據(jù)概率從群體中選出一個計算機程序個體，然后用合適的操作作用于該計算機程序個體。把現(xiàn)有的計算機程序復(fù)制到新的群體中。通過遺傳隨機重組兩個現(xiàn)有的程序,創(chuàng)造出新的計算機程序個體。3.在后代中適應(yīng)值最高的計算機程序個體被指定為進化程序設(shè)計的結(jié)果。這一結(jié)果可能是問題的解或近似解。二.進化策略的具體步驟:552.3謂詞邏輯法一.謂詞邏輯的簡要回顧

1.命題與謂詞命題:表示客觀事實的語句李明是個工人 LIWORKER或L把謂語部分提出WORKER(LI)WORKER(WANG)引入變量、函數(shù)和量詞(x)(HUMAN(x)->NEED-STUDY(x))(x)TEACHER(brother(x))注:我們只討論一階謂詞演算.2.3謂詞邏輯法一.謂詞邏輯的簡要回顧562.合適公式(well-formedformula)原子(謂詞)公式原子公式::=謂詞名+“(”+項[,項]+“)”項::=常量|變量|函數(shù)函數(shù)::=函數(shù)名+“(”+參數(shù)[,參數(shù)]+“)”合適公式原子謂詞公式是合適公式;若A是合適公式,則~A也是合適公式;若A和B都是合適公式,則AB,AVB,AB也都是合適公式;若A是合適公式,x為任何變量,則(x)A和(x)A也是合適公式;只有按上述規(guī)則產(chǎn)生的公式才是合適公式.(有限步)2.合適公式(well-formedformula)57

3.用謂詞公式表達知識

例:任何整數(shù)或者是正數(shù)或者是負數(shù).用I(x)表示“x是整數(shù)”,用P(x)表示“x是正數(shù)”,用N(x)表示“x是負數(shù)”.

(x)(I(x)(P(x)VN(x)))

例:用謂詞邏輯表達積木世界.3.用謂詞公式表達知識58一.基本概念

語義網(wǎng)絡(luò)是一種用實體及其語義關(guān)系來表達知識的有向圖.結(jié)點:代表實體,表示各種事物、概念、情況、屬性、狀態(tài)、事件、動作等;

弧:代表語義關(guān)系,表示它所連接的兩個實體之間的語義聯(lián)系.

在語義網(wǎng)絡(luò)中,每一個結(jié)點和弧都必須帶有標識,這些標識用來說明它所代表的實體或語義.二.以個體為中心的語義網(wǎng)絡(luò)1.實例聯(lián)系

2.4語義網(wǎng)絡(luò)法一.基本概念2.4語義網(wǎng)絡(luò)法59

2.泛化聯(lián)系

3.聚集聯(lián)系2.泛化聯(lián)系60

4.屬性聯(lián)系三.以謂詞為中心的語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)表示法和謂詞邏輯表示法之間有著對應(yīng)的表示能力.

1.二元謂詞4.屬性聯(lián)系61

2.n元謂詞n元謂詞可轉(zhuǎn)化為n個二元謂詞的合取例:“李明給王宏<<圍城>>”3.連接詞的表達例:“李明給王宏<<圍城>>而且王宏讀了<<圍城>>”2.n元謂詞62

4.量詞的表達存在量詞的表達,例:“某個大學(xué)生讀過<<圍城>>”

人工智能大學(xué)課件63全稱量詞的表達,采用語義網(wǎng)絡(luò)分塊化技術(shù).例:“所有的大學(xué)生都讀過<<圍城>>”人工智能大學(xué)課件64三.語義網(wǎng)絡(luò)的推理1.網(wǎng)絡(luò)匹配2.繼承推理3.網(wǎng)絡(luò)演繹四.語義網(wǎng)絡(luò)的特點1.優(yōu)點

結(jié)構(gòu)性,聯(lián)想性,自索引性,自然性2.缺點推理規(guī)則不十分明了表達范圍有限，一旦結(jié)點個數(shù)太多，網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，推理就難以進行

三.語義網(wǎng)絡(luò)的推理652.5框架表示一.框架是一種結(jié)構(gòu)性的知識表達方法框架的作用:表示事物各方面的屬性表示事物之間的類屬關(guān)系事物的特征和變異識別、分析、預(yù)測事物及其行為一.框架的基本結(jié)構(gòu)例:有下列描述“2000年5月13日,在西藏的阿里地區(qū)發(fā)生了里氏5.3級地震,傷亡24人,死亡1人,財產(chǎn)損失2000萬人民幣”把他表示為框架如下:Frame(框架名):地震Slot1(槽名):時間:2000年5月13日Slot2(槽名):地點:西藏的阿里地區(qū)2.5框架表示一.框架是一種結(jié)構(gòu)性的知識表達方法66

Slot3(槽名):震級:里氏5.3級Slot4(槽名):傷亡人數(shù):24Slot5(槽名):死亡人數(shù):1Slot6(槽名):財產(chǎn)損失:2000萬人民幣框架的一般結(jié)構(gòu)<框架名><槽1><側(cè)面11><值111><值112>...<側(cè)面12><值121><值122>......<槽2><側(cè)面21><值211><值212>.........<槽n><側(cè)面n1><值n11>......有兩種特殊的側(cè)面:默認值側(cè)面,附加過程側(cè)面Slot3(槽名):震級:里氏5.3級67三.框架的推理1.匹配,是不完全匹配2.繼承推理3.填槽四.附加過程側(cè)面的類型1.if-needed2.if-added3.if-removed三.框架的推理683456789101112131415161718192021★2324★26272829303112活結(jié)點表1121124224844816881616817881717884944918991818919919194425225105510209991010202010211010212110105115511★深度優(yōu)先搜索示意圖3456789101112131415161718192026912345678910111213141516171819★21222324★26272829303112345678910111213141516171819★活結(jié)點表234567891011121314151617181912345678910123456789寬度優(yōu)先搜索演示圖12345678910111213141516171819★70寬度優(yōu)先2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652567312384765目標8234187654寬度優(yōu)先23232871深度優(yōu)先231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目標深度優(yōu)先232328723.2啟發(fā)式搜索一.基本思想也叫LC-搜索（按成本最小的原則從活結(jié)點表中作選擇）需要定義一個評價函數(shù)c，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展.二.評價函數(shù) f(n)=h(n)+g(n)

f(n):評價函數(shù)或叫作成本函數(shù),表示從開始到目前,再到找到一個問題解的所花費的最小成本的估計.g(n):表示從開始到目前所花費的成本值或其估計.h(n):啟發(fā)函數(shù),表示從目前到找到一個問題的最小成本的一個估計.3.2啟發(fā)式搜索一.基本思想73345678910111213141516171819★21222324★26272829303112活結(jié)點表112233244554889951010111110★1245LC-搜索示意圖345678910111213141516171819★2174三.舉例:九宮重排83647■5初始狀態(tài)1238■4765目標狀態(tài)h(X)：結(jié)點X的格局與目標格局相比，位置不符合的將牌數(shù)目；三.舉例:九宮重排83初始狀態(tài)123752831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■65■2318476523■184765123■847651238■4765123784■650+41+51+31+52+32+32+43+3

3+43+2

3+44+15+05+2目標2832832764.3人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)一.人工神經(jīng)網(wǎng)絡(luò)的基本要素:.神經(jīng)單元.輸入與輸出.輸出函數(shù).激勵函數(shù).連接模式.傳播規(guī)則.學(xué)習(xí)法則4.3人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)一.人工神經(jīng)網(wǎng)絡(luò)的基本要素:77二.人工神經(jīng)網(wǎng)絡(luò)模型

二.人工神經(jīng)網(wǎng)絡(luò)模型78三.人工神經(jīng)網(wǎng)絡(luò)各部分特性1.神經(jīng)單元

分為輸入單元,輸出單元和隱單元每個單元有激活值,可以是連續(xù)實數(shù)值,也可以是離散整數(shù)值2.輸入與輸出

從網(wǎng)絡(luò)外部到網(wǎng)絡(luò)內(nèi)部的為輸入信號從網(wǎng)絡(luò)內(nèi)部到網(wǎng)絡(luò)外部的為輸出信號三.人工神經(jīng)網(wǎng)絡(luò)各部分特性793.輸出函數(shù)

單元的輸出信號與單元激活值的映射關(guān)系可以是等值函數(shù),也可以是閾值函數(shù)4.激勵函數(shù)單元的總輸入信號與單元激活值的映射關(guān)系可以是等值函數(shù),也可以是閾值函數(shù)或可微的連續(xù)函數(shù)3.輸出函數(shù)805.連接模式

網(wǎng)絡(luò)中所有單元連接強度(權(quán)值)構(gòu)成的矩陣6.傳播規(guī)則

某個神經(jīng)單元所接受的總輸入與其它單元對該單元輸出之間的關(guān)系,最常用的為加權(quán)傳播法則.5.連接模式817.學(xué)習(xí)法則神經(jīng)網(wǎng)絡(luò)的運行包括兩個階段：1.訓(xùn)練或?qū)W習(xí)階段向神經(jīng)網(wǎng)絡(luò)提供一系列輸入－輸出數(shù)據(jù)組,通過數(shù)值計算方法和參數(shù)優(yōu)化技術(shù),使節(jié)點連接的權(quán)值不斷調(diào)整,直到從給定的輸入能產(chǎn)生所期望的輸出.22.預(yù)測（應(yīng)用）階段以訓(xùn)練好的網(wǎng)絡(luò),對未知的樣本進行預(yù)測

人工神經(jīng)網(wǎng)絡(luò)的主要學(xué)習(xí)算法.有師學(xué)習(xí).無師學(xué)習(xí).強化學(xué)習(xí)7.學(xué)習(xí)法則824.4線性模型與感知機一.線性網(wǎng)絡(luò)模型特征

1.只有輸入單元和輸出單元,沒有隱單元2.單元激活值為連續(xù)實數(shù)值3.輸出函數(shù)和激活函數(shù)均為等值函數(shù)4.采用加權(quán)傳播規(guī)則線性網(wǎng)絡(luò)模型等價于線形方程組(請課后自行分析)多層線性模型可以找到等價的雙層線形模型(既隱單元對線形模型是多余的)請在作業(yè)中證明.4.4線性模型與感知機一.線性網(wǎng)絡(luò)模型特征83二.線性閾值模型的特征

1.既有輸入單元和輸出單元,也有隱單元2.單元激活值為{0,1}3.輸出函數(shù)為等值函數(shù)4.激活函數(shù)為閾值函數(shù)5.采用加權(quán)傳播規(guī)則二.線性閾值模型的特征84三.兩層線性閾值模型(感知機)這是一個表達或邏輯的模型它可以用delta學(xué)習(xí)法則學(xué)習(xí)

三.兩層線性閾值模型(感知機)85感知機無法表達異或邏輯(請在課后作業(yè)證明)異或邏輯甚至更復(fù)雜的布爾代數(shù)只能用多層線形閾值模型表達,但無法找到合適的學(xué)習(xí)法則.感知機局限性的分析:感知機無法表達異或邏輯(請在課后作業(yè)證明)864.5BP模型及應(yīng)用一.BP模型(反向傳播網(wǎng)絡(luò))的特征

1.既有輸入單元和輸出單元,也有隱單元2.單元激活值為連續(xù)實數(shù)值3.輸出函數(shù)為等值函數(shù)4.激活函數(shù)為非遞減的可微函數(shù)例如Sigmoid函數(shù),非對稱Sigmoid函數(shù)為f(X)=1/(1+e-x),對稱Sigmoid函數(shù)f(X)=(1-e-x)/(1+e-x).5.采用加權(quán)傳播規(guī)則6.學(xué)習(xí)算法采用的是梯度下降法，它使期望輸出與實際輸出之間的誤差平方和最小.4.5BP模型及應(yīng)用一.BP模型(反向傳播網(wǎng)絡(luò))的特征87設(shè)誤差e采用下式表示：

其中,Yi＝f〔W*·Xi]是對應(yīng)第i個樣本Xi的實時輸出Yi是對應(yīng)第i個樣本Xi的期望輸出.要使誤差e最小，可先求取e的梯度：設(shè)誤差e采用下式表示：88二.BP模型的應(yīng)用范圍及局限.BP模型廣泛應(yīng)用于模式識別,預(yù)測,信號處理等領(lǐng)域.經(jīng)數(shù)學(xué)證明,它可以表達任意連續(xù)函數(shù).其缺點是學(xué)習(xí)時間長,收斂慢,且容易陷入局部最小,原因是誤差曲面復(fù)雜.二.BP模型的應(yīng)用范圍及局限89三.BP模型的應(yīng)用舉例

實例：應(yīng)用BP網(wǎng)絡(luò)預(yù)測氣候變化對雅礱江流域徑流的影響.經(jīng)分析,在諸多氣候因子中,流域內(nèi)年均氣溫和年均降水量是影響流域年均徑流的兩個主要因子,若把氣溫和降水看作輸入,徑流看作輸出,可用BP網(wǎng)絡(luò)來研究氣溫和降水變化對流域徑流的影響.建立三層BP網(wǎng)絡(luò)(輸入層、輸出層和一個隱蔽層),以年均氣溫和年均降水量作為BP網(wǎng)絡(luò)輸入層的輸入單元,年均徑流量為網(wǎng)絡(luò)輸出層的輸出單元.用1960到1990年共31年實測的年均氣溫、降水和徑流量系列資料(即31個樣本對)對網(wǎng)絡(luò)進行訓(xùn)練、檢驗,其中1960—1982年資料作為訓(xùn)練樣本，1983-1990年資料作為檢驗樣本。三.BP模型的應(yīng)用舉例90BP網(wǎng)絡(luò)在雅礱江流域年均流量的擬合與預(yù)測精度(%)

項目BP網(wǎng)絡(luò)模型線性回歸模型備注平均相對誤差5.996.65擬合最大相對誤差17.0018.52平均相對誤差7.819.33預(yù)測最大相對誤差21.0325.46

摘自<<水利學(xué)報>>99年第1期BP網(wǎng)絡(luò)在雅礱江流域年均流量的擬合與預(yù)測精度(%)915.1遺傳算法一.概述

1.遺傳算法(GeneticAlgorithms,簡稱GA)思想來源于生物進化過程,它是基于進化過程中的信息遺傳機制和優(yōu)勝劣汰的自然選擇原則的搜索算法(以字符串表示狀態(tài)空間).

2.GA由美國J.H.Holland教授于1975年首先提出,并以其提出的圖式定理作為理論基礎(chǔ).

12/11/20225.1遺傳算法一.概述12/10/2022923.GA特別適用于傳統(tǒng)數(shù)學(xué)難以解決的復(fù)雜的優(yōu)化問題,如TSP問題.

4.GA屬于鄰域搜索的一類,它用概率方式產(chǎn)生新的鄰域個體.

5.簡單的GA存在參數(shù)難以控制,容易陷入局部收斂等缺陷,現(xiàn)在的趨勢是把它與其他的優(yōu)化算法結(jié)合起來取長補短.3.GA特別適用于傳統(tǒng)數(shù)學(xué)難以解決的復(fù)雜的優(yōu)化問題,如TS93二.遺傳算法的基本機理

1.編碼與解碼遺傳算法先將搜索結(jié)構(gòu)編碼為字符串形式,每個字符串結(jié)構(gòu)被稱為個體(染色體).相反將字符串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫解碼.編碼方法有二進制編碼,實數(shù)編碼,符號編碼等.

二.遺傳算法的基本機理94

2.染色體優(yōu)劣的度量----適應(yīng)度每個染色體與其適應(yīng)度的對應(yīng)關(guān)系是適應(yīng)度函數(shù),它應(yīng)該有效反映每個染色體與問題的最優(yōu)解染色體之間的差距.3.遺傳操作

選擇(復(fù)制),根據(jù)個體的適應(yīng)度函數(shù)值決定它在下一代被淘汰還是被遺傳.

交叉將被選擇的兩個個體作為母體進行部分子串的交換.2.染色體優(yōu)劣的度量----適應(yīng)度95

變異就是改變?nèi)旧w的某些基因.三.遺傳算法的準備工作

1.確定表示方案;2.確定適應(yīng)值的度量;3.確定控制該算法的參數(shù)和變量;4.確定怎樣指定結(jié)果及程序運行結(jié)束的標準.人工智能大學(xué)課件96四.遺傳算法的具體步驟1.隨機產(chǎn)生一個由固定長度字符串組成的初始群體;2.對于字符串群體,迭代地執(zhí)行下述步驟,直到選種標準被滿足為止:計算群體中的每個個體字符串的適應(yīng)值;應(yīng)用下述三種操作(至少前兩種)來產(chǎn)生新的群體:復(fù)制:把現(xiàn)有的個體字符串復(fù)制到新的群體中.雜交:通過遺傳重組隨機選擇兩個現(xiàn)有的子字符串,產(chǎn)生新的字符串.變異:將現(xiàn)有字符串中某一位的字符隨機變異.人工智能大學(xué)課件97

3.把在后代中出現(xiàn)的最高適應(yīng)值的個體字符串指定為遺傳算法運行的結(jié)果.這一結(jié)果可以是問題的解(或近似)4.簡單的雜交操作分為三步從當前群體B(t)中選擇兩個結(jié)構(gòu)：

隨機選擇一個整數(shù)交換a和a‘中位置x左邊的元素,產(chǎn)生兩個新的結(jié)構(gòu)：3.把在后代中出現(xiàn)的最高適應(yīng)值的個體字符串指定為遺傳算985.簡單的變異操作過程如下:每個位置的字符變量都有一個變異概率,各位置互相獨立.通過隨機過程選擇發(fā)生變異的位置：產(chǎn)生一個新結(jié)構(gòu)其中是從對應(yīng)位置的字符變量的值域中隨機選擇的一個取值?？梢酝瑯拥玫?.簡單的變異操作過程如下:99GEN=0概率地選擇遺傳操作隨機創(chuàng)建初始群體是否滿足選中標準？計算群體中每個個體的適應(yīng)值i:=0i:=M指定結(jié)果結(jié)束GEN:=GEN+1是是否GEN=0概率地選擇遺傳操作隨機創(chuàng)建初始群體是否滿足選中標準100概率地選擇遺傳操作根據(jù)適應(yīng)值選擇一個個體完成雜交i:=i+1i:=i+1完成繁殖p(r)繁殖基于適應(yīng)值選擇兩個個體把新的兩個孩子加到群體中p(c)雜交變異p(m)把新的孩子加入到群體中完成變異根據(jù)適應(yīng)值選擇一個個體把變異后個體加入到群體中概率地選擇遺傳操作根據(jù)適應(yīng)值選完成雜交i:=i+1i:=i+101五.遺傳算法與傳統(tǒng)優(yōu)化算法的主要不同遺傳算法不是直接作用在參變量集上,而是利用參變量集的某種編碼;遺傳算法不是從單個點,而是在群體中