人工智能09貝葉斯網(wǎng)絡(luò)

1、Bayesian networks貝葉斯網(wǎng)絡(luò)Frequentistvs.Bayesian客觀vs.主觀Frequentist（頻率主主義者）:概率是長長期的預(yù)預(yù)期出現(xiàn)現(xiàn)頻率. P(A)=n/N, where nisthe numberoftimeseventA occursinN opportunities.“某事發(fā)生生的概率率是0.1” 意味味著0.1是在無窮窮多樣本本的極限限條件件下能夠夠被觀察察到的比比例但是，在在許多情情景下不不可能進(jìn)進(jìn)行重復(fù)復(fù)試驗(yàn)發(fā)生第三三次世界界大戰(zhàn)的的概率是是多少?Bayesian:degreeofbelief.Itisa measureofthe plausib

2、ility（似然性性）ofaneventgivenincomplete knowledge.相信的程程度，是是在不確確定知識識的環(huán)境境下對事事件似然然性的衡衡量Probability概率Probabilityisa rigorous formalismforuncertain knowledge概率是對對不確定定知識一一種嚴(yán)密密的形式式化方法法Jointprobabilitydistributionspecifiesprobabilityofeveryatomicevent全聯(lián)合概概率分布布指定了了對隨機(jī)機(jī)變量的的每種完完全賦值值，即每每個(gè)原子事件件的概率Queries canbeanswer

3、edbysumming overatomic events可以通過過把對應(yīng)應(yīng)于查詢詢命題的的原子事事件的條條目相加加的方式式來回答答查詢Fornontrivialdomains,wemust findawaytoreduce thejointsizeIndependenceandconditionalindependenceprovide thetoolsIndependence/Conditional IndependenceAandBareindependentiffP(A|B) =P(A)orP(B|A) =P(B)orP(A,B)=P(A)P(B)Aisconditionally in

4、dependentofBgivenC:P(A|B,C) =P(A|C)在大多數(shù)數(shù)情況下下，使用用條件獨(dú)獨(dú)立性能能將全聯(lián)聯(lián)合概率率的表示示由n的指數(shù)關(guān)關(guān)系減為為n的線性關(guān)關(guān)系。Conditionalindependenceisour mostbasicand robustform of knowledgeaboutuncertainenvironments.ProbabilityTheoryProbabilitytheorycan be expressedintermsoftwosimple equations概率理論論可使用用兩個(gè)簡簡單線性性方程來來表達(dá)SumRule（加法規(guī)規(guī)則）變量的概概率

5、是通通過邊緣緣化或者者求和其其他變量量獲得的的Product Rule（乘法規(guī)規(guī)則）用條件表表達(dá)聯(lián)合合概率所有的概概率推理理和學(xué)習(xí)習(xí)相當(dāng)于于不斷重重復(fù)加法法和乘法法法則大綱Graphicalmodels（概率圖圖模型）Bayesiannetworks Syntax（語法） Semantics（語義）Inference（推導(dǎo)）inBayesiannetworks什么是圖圖模型？概率分布布的圖表表示概率論和和圖論的的結(jié)合 Alsocalled概率圖模模型 Theyaugmentanalysisinstead of using purealgebra（代數(shù)）What is aGraph? Consi

6、sts of nodes (also calledvertices)and links (also callededgesorarcs)在概率圖圖模型中中每個(gè)節(jié)點(diǎn)點(diǎn)表示一一個(gè)隨機(jī)機(jī)變量(or一組隨機(jī)機(jī)變量)邊表示變變量間的的概率關(guān)關(guān)系GraphicalModels in CS處理不確確定性和和復(fù)雜性性的天然然工具貫穿整個(gè)個(gè)應(yīng)用數(shù)數(shù)學(xué)和工工程領(lǐng)域域圖模型中中最重要要的思想想是模塊塊性概念念 acomplexsystemisbuiltbycombining simplerparts.Whyare GraphicalModelsuseful概率理論論提供了了“黏合合劑”whereby使每個(gè)部部分連接

7、接起來,確保系統(tǒng)統(tǒng)作為一一個(gè)整體體是一致致的提供模型型到數(shù)據(jù)據(jù)的連接接方法.圖理論方方面提供供:直觀的接接口 by which humanscanmodelhighly-interacting setsofvariables數(shù)據(jù)結(jié)構(gòu)構(gòu) thatlendsitself naturallytodesigningefficient general-purpose（通用的的）algorithmsGraphicalmodels:統(tǒng)一的框框架考慮傳統(tǒng)統(tǒng)的多變變量的概概率系統(tǒng)統(tǒng)作為一一般基礎(chǔ)礎(chǔ)形式的的實(shí)例 mixturemodels（混合模模型）, factoranalysis（因子分分析）, hidden

8、Markovmodels,Kalmanfilters（卡爾曼曼濾波器器）, etc.在系統(tǒng)工工程，信信息論，模式識識別和統(tǒng)統(tǒng)計(jì)力學(xué)學(xué)中被用用到優(yōu)勢:在某一領(lǐng)領(lǐng)域中的的專業(yè)技技術(shù)能夠夠在該領(lǐng)領(lǐng)域中相相互轉(zhuǎn)化化并被充充分利用用 Provides naturalframework fordesigningnew systems圖模型在在機(jī)器學(xué)學(xué)習(xí)中的的角色形象化概概率模型型結(jié)構(gòu)的的簡單方方法Insightsinto propertiesofmodelConditionalindependence propertiesbyinspectinggraph執(zhí)行推理理和學(xué)習(xí)習(xí)表示為為圖形化化操作需需要復(fù)雜雜

9、的計(jì)算算圖的方向向性有向圖模模型方向取決決于箭頭頭貝葉斯網(wǎng)網(wǎng)絡(luò)隨機(jī)變量量間的因因果關(guān)系系 MorepopularinAIandstatistics無向圖模模型邊沒有箭箭頭 Markovrandomfields（馬爾科科夫隨機(jī)機(jī)場）更適合表表達(dá)變量量之間的的軟約束束 MorepopularinVisionand physicsBayesiannetworks一種簡單單的，圖圖形化的的數(shù)據(jù)結(jié)結(jié)構(gòu)，用用于表示示變量之之間的依依賴關(guān)關(guān)系（條條件獨(dú)立立性），為任何何全聯(lián)合合概率分分布提供供一種簡簡明的的規(guī)范。Syntax語法:aset of nodes,oneper variableadirected（

10、有向）, acyclic（無環(huán)）graph(link directinfluences)aconditionaldistribution foreach nodegivenits parents:P(Xi| Parents(Xi)量化其父父節(jié)點(diǎn)對對該節(jié)點(diǎn)點(diǎn)的影響響Inthesimplestcase,conditionaldistribution represented as aconditionalprobabilitytable條件概率率表(CPT)givingthedistributionoverXiforeachcombinationofparentvaluesExampleTopolo

11、gy（拓?fù)浣Y(jié)結(jié)構(gòu)）ofnetwork encodesconditionalindependence assertions:Weather獨(dú)立于其其他變量量ToothacheandCatchareconditionallyindependentgivenCavityExample我晚上在在單位上上班，此此時(shí)鄰居居John給我打電電話說我我家警報(bào)報(bào)響了，但是鄰鄰居Mary沒有給打打電話。有時(shí)輕輕微的地地震也會會引起警警報(bào)。那那么我家家真正遭遭賊了嗎嗎？Variables:Burglary（入室行行竊）,Earthquake,Alarm,JohnCalls,MaryCalls網(wǎng)絡(luò)拓?fù)鋼浣Y(jié)構(gòu)反反映出因

12、因果關(guān)系系:Aburglar cansetthe alarm off An earthquakecan setthealarmoffThe alarm cancauseMary to callThealarmcan cause JohntocallExample contd.Compactness（緊致性性）A CPTforBooleanXiwithkBoolean parentshas2krows forthecombinations of parentvalues一個(gè)具有有k個(gè)布爾父父節(jié)點(diǎn)的的布爾變變量的條條件概率率表中有有2k個(gè)獨(dú)立的的可指定定概率Each rowrequiresonen

13、umberpforXi= true(the numberforXi=falseisjust1-p)Ifeach variable hasnomore thankparents,thecompletenetworkrequiresO(n2k)numbersI.e.,growslinearlywithn, vs.O(2n)forthe fulljointdistributionForburglarynet,1 +1+ 4+2 +2= 10 numbers(vs.25-1= 31)Globalsemantics（全局語語義）Thefulljointdistributionisdefinedasthe

14、productofthelocalconditionaldistributions:全聯(lián)合概概率分布布可以表表示為貝貝葉斯網(wǎng)網(wǎng)絡(luò)中的的條件概概率分布布的乘積積Globalsemantics（全局語語義）Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:全聯(lián)合概概率分布布可以表表示為貝貝葉斯網(wǎng)網(wǎng)絡(luò)中的的條件概概率分布布的乘積積LocalsemanticsLocalsemantics: eachnodeisconditionally independent of itsnondescend

15、ants（非后代代）givenitsparents給定父節(jié)節(jié)點(diǎn)，一一個(gè)節(jié)點(diǎn)點(diǎn)與它的的非后代代節(jié)點(diǎn)是是條件獨(dú)獨(dú)立的Theorem:LocalsemanticsglobalsemanticsCausalChains因果鏈一個(gè)基本本形式： Is XindependentofZgivenY?Evidencealongthechain“blocks”the influenceCommonCause共同原因因另一個(gè)基基礎(chǔ)的形形態(tài): twoeffects of thesame causeAre Xand Zindependent?Are Xand ZindependentgivenY?Observingth

16、e cause blocksinfluencebetweeneffects.CommonEffect共同影響響最后一種種配置形形態(tài): twocausesofoneeffect(v-structures) AreX andZ independent? Yes:rememberthe ballgame andtheraincausingtraffic,nocorrelation? AreX andZ independent given Y? No:rememberthat seeingtraffic puttherainand theballgameincompetition?This is ba

17、ckwardsfrom theothercases Observingtheeffect enablesinfluence betweencauses.構(gòu)造貝葉葉斯網(wǎng)絡(luò)絡(luò)Need amethod suchthata seriesoflocally testable assertionsofconditionalindependence guaranteesthe required globalsemantics需要一種種方法使使得局部部的條件件獨(dú)立關(guān)關(guān)系能夠夠保證全全局語義義得以成成立ChooseanorderingofvariablesX1, ,XnFori= 1tonaddXitothen

18、etworkselect parentsfromX1, ,Xi-1such thatP(Xi| Parents(Xi)=P(Xi| X1, .Xi-1)該父親選選擇保證證了全局局語義:構(gòu)造貝葉葉斯網(wǎng)絡(luò)絡(luò)要求網(wǎng)絡(luò)絡(luò)的拓?fù)鋼浣Y(jié)構(gòu)確確實(shí)反映映了合適適的父節(jié)節(jié)點(diǎn)集對對每個(gè)變變量的那那些直接接影響。添加節(jié)點(diǎn)點(diǎn)的正確確次序是是首先添添加“根根本原因因”節(jié)點(diǎn)點(diǎn)，然后后加入受受它們直直接影響響的變量量，以此此類推。ExampleExampleExampleExampleExampleExample contd.在非因果果方向決決定條件件獨(dú)立性性是很難難的(Causal modelsandconditional

19、independence seemhardwired forhumans!)Network is lesscompact:1+ 2+4 +2+ 4=13numbers needed因果關(guān)系系?當(dāng)貝葉斯斯網(wǎng)絡(luò)反反映真正正的因果果模式時(shí)時(shí):Oftensimpler(nodeshavefewerparents) Often easiertothinkabout Often easiertoelicitfromexperts（專家） BNs不一定必必須是因因果有時(shí)無因因果關(guān)系系的網(wǎng)絡(luò)絡(luò)是存在在的(especiallyifvariablesare missing)箭頭反映映相關(guān)性性，而不不是因果果關(guān)系箭

20、頭的真真正含義義是什么么?Topologymay happentoencodecausal structureTopologyreallyencodesconditionalindependenceInferenceinBayesiannetworks推理任務(wù)務(wù)簡單查詢詢:計(jì)算后驗(yàn)驗(yàn)概率P(Xi|E=e)e.g.,P(NoGas|Gauge油表=empty, Lights=on,Starts=false)聯(lián)合查詢詢:P(Xi,Xj|E=e) =P(Xi|E=e)P(Xj|Xi,E=e)最優(yōu)決策策: decision networks includeutilityinformation;prob

21、abilisticinferencerequiredforP(outcome|action, evidence)通過枚舉舉進(jìn)行推推理上一章解解釋了任任何條件件概率都都可以通通過將全全聯(lián)合分分布表中中的某些些項(xiàng)相加加而計(jì)算算得到在貝葉斯斯網(wǎng)絡(luò)中中可以通通過計(jì)算算條件概概率的乘乘積并求求和來回回答查詢詢。通過枚舉舉進(jìn)行推推理上一章解解釋了任任何條件件概率都都可以通通過將全全聯(lián)合分分布表中中的某些些項(xiàng)相加加而計(jì)算算得到Evaluation tree變量消元元法Variableelimination（變量消消元）: carry outsummations right-to-left, storingi

22、ntermediate results(factors：因子) to avoid recomputation精確推理理的復(fù)雜雜度Singlyconnected networks單聯(lián)通網(wǎng)網(wǎng)絡(luò)(orpolytrees多樹): anytwonodesare connectedbyatmost one(undirected)path timeand space costofvariableeliminationare O(dkn)多樹上的的變量消消元的時(shí)時(shí)間和空空間復(fù)雜雜度都與與網(wǎng)絡(luò)規(guī)規(guī)模呈線線性關(guān)系系。Multiplyconnectednetworks多聯(lián)通網(wǎng)網(wǎng)絡(luò):can reduce3SAT to

23、 exact inference NP-hardequivalent to counting 3SATmodels #P-completeExample:NaveBayesmodel單一父親親變量和和一批孩孩子變量量，孩子子變量在在給定父父親變量量下是相相互獨(dú)立立的NaveBayesmodelTotalnumberofparameters（參數(shù)）islinearinnExample:垃圾郵件件檢測想象一下下試圖去去自動檢檢測垃圾圾郵件的的問題.一個(gè)簡單單的方案案是只檢檢測主題題，然后后根據(jù)郵郵件的標(biāo)標(biāo)題檢查查一些簡簡單的特特征來嘗嘗試識別別垃圾郵郵件.我們先考考慮兩個(gè)個(gè)簡單的的特征:Caps:

24、是否標(biāo)題題是徹底底大寫的的Free:是否標(biāo)題題中包含含大寫或或小寫的的單詞freee.g.:a messagewiththesubjectheader“NEWMORTGAGERATE“islikelytobespam.Similarly,for“Money forFree”,“FREElunch”,etc.Example:垃圾郵件件檢測模型的構(gòu)構(gòu)建基于于以下三三個(gè)隨機(jī)機(jī)變量,Caps,FreeandSpam, eachofwhichtakeonthevalues Y(forYes) or N(forNo)Caps= Yifand onlyifthe subjectofthe messagedo

25、esnotcontainlowercaselettersFree= Yifand onlyifthe wordfree appearsinthe subject(lettercase is ignored)Spam= Yifand onlyifthe messageisspamP(Free,Caps,Spam)=P(Spam )P(Caps|Spam) P(Free|Spam)Example:垃圾郵件件檢測P(Free, Caps, Spam)=P(Spam)P(Caps|Spam)P(Free|Spam)Example:垃圾郵件件檢測Example:垃圾郵件件檢測Example:Learni

26、ngtoclassifytextdocuments文本分類類是在文文檔所包包含的文文本基礎(chǔ)礎(chǔ)上，把把給定的的文檔分分配到到固定類類別集合合中某一一個(gè)類別別的任務(wù)務(wù)。這個(gè)個(gè)任務(wù)中中常常用用到樸樸素貝葉葉斯模型型。在這這些模型型中，查查詢變量量是文檔檔類別，“結(jié)結(jié)果”變變量則是是語言中中每個(gè)詞詞是否出出現(xiàn)。我我們假設(shè)設(shè)文檔檔中的詞詞的出現(xiàn)現(xiàn)都是獨(dú)獨(dú)立的，其出現(xiàn)現(xiàn)頻率由由文檔類類別確定定。a.準(zhǔn)確地解解釋當(dāng)給給定一組組類別已已經(jīng)確定定的文檔檔作為“訓(xùn)練數(shù)數(shù)據(jù)”時(shí)時(shí)，這樣樣的模型型是如何何構(gòu)造的的。b.準(zhǔn)確地解解釋如何何對新文文檔進(jìn)行行分類。c.這里獨(dú)立立性假設(shè)設(shè)合理嗎嗎？請討討論。Example:L

27、earningtoclassifytextdocuments模型包含含先驗(yàn)概概率P(Category)和條件概率率P(wordi|Category) P(Category=c)isestimated as thefractionofalldocuments thatare of category c P(wordi =true|Category=c)isestimatedasthe fraction of documentsofcategoryc thatcontainword iTwentyNewsgroupsGiven1000 training documentsfrom eachgroup. Learn to classify newdocumentsaccording to which newsgroupitcame fromNaveBayes:89% classification accuracyLearningCurvefor20Newsgrou