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

Bayesiannetworks

貝葉斯網(wǎng)絡(luò)Frequentistvs.Bayesian客觀vs.主觀Frequentist（頻率主義者）:概率是長期的預(yù)期出現(xiàn)頻率.P(A)=n/N,wherenisthenumberoftimeseventAoccursinNopportunities.“某事發(fā)生的概率是0.1”意味著0.1是在無窮多樣本的極限

條件下能夠被觀察到的比例

但是，在許多情景下不可能進(jìn)行重復(fù)試驗(yàn)

發(fā)生第三次世界大戰(zhàn)的概率是多少?Bayesian:degreeofbelief.Itisameasureoftheplausibility（似然性）ofaneventgivenincompleteknowledge.相信的程度，是在不確定知識(shí)的環(huán)境下對(duì)事件似然性的衡量Probability概率Probabilityisarigorousformalismforuncertainknowledge概率是對(duì)不確定知識(shí)一種嚴(yán)密的形式化方法Jointprobabilitydistributionspecifiesprobabilityofeveryatomicevent全聯(lián)合概率分布指定了對(duì)隨機(jī)變量的每種完全賦值，即每個(gè)原子事件的概率Queriescanbeansweredbysummingoveratomicevents可以通過把對(duì)應(yīng)于查詢命題的原子事件的條目相加的方式來回答查詢Fornontrivialdomains,wemustfindawaytoreducethejointsize

IndependenceandconditionalindependenceprovidethetoolsIndependence

/ConditionalIndependenceAandBareindependentiff

P(A|B)=P(A)orP(B|A)=P(B)orP(A,B)=P(A)P(B)AisconditionallyindependentofBgivenC:

P(A|B,C)=P(A|C)在大多數(shù)情況下，使用條件獨(dú)立性能將全聯(lián)合概率的表示由n的指數(shù)關(guān)系減為n的線性關(guān)系。Conditionalindependenceisourmostbasicandrobustformofknowledgeaboutuncertainenvironments.ProbabilityTheoryProbabilitytheorycanbeexpressedintermsoftwosimpleequations概率理論可使用兩個(gè)簡單線性方程來表達(dá)–SumRule（加法規(guī)則）?變量的概率是通過邊緣化或者求和其他變量獲得的–ProductRule（乘法規(guī)則）?用條件表達(dá)聯(lián)合概率所有的概率推理和學(xué)習(xí)相當(dāng)于不斷重復(fù)加法和乘法法則大綱Graphicalmodels（概率圖模型）Bayesiannetworks

–Syntax（語法）

–Semantics（語義）Inference（推導(dǎo)）inBayesiannetworks

什么是圖模型？概率分布的圖表示

–概率論和圖論的結(jié)合

?Alsocalled概率圖模型?Theyaugmentanalysisinsteadofusingpure

algebra（代數(shù)）WhatisaGraph??Consistsofnodes(alsocalledvertices)andlinks(alsocallededgesorarcs)?在概率圖模型中

–每個(gè)節(jié)點(diǎn)表示一個(gè)隨機(jī)變量(or一組隨機(jī)變量)

–邊表示變量間的概率關(guān)系GraphicalModelsinCS?處理不確定性和復(fù)雜性的天然工具

–貫穿整個(gè)應(yīng)用數(shù)學(xué)和工程領(lǐng)域?圖模型中最重要的思想是模塊性概念

–acomplexsystemisbuiltbycombiningsimplerparts.WhyareGraphicalModelsuseful?概率理論提供了“黏合劑”whereby

–使每個(gè)部分連接起來,確保系統(tǒng)作為一個(gè)整體是一致的

–提供模型到數(shù)據(jù)的連接方法.?圖理論方面提供:

–直觀的接口

?bywhichhumanscanmodelhighly-interactingsetsofvariables

–數(shù)據(jù)結(jié)構(gòu)

?thatlendsitselfnaturallytodesigningefficientgeneral-purpose（通用的）algorithmsGraphicalmodels:統(tǒng)一的的框架架?考慮傳傳統(tǒng)的的多變變量的的概率率系統(tǒng)統(tǒng)作為為一般般基礎(chǔ)礎(chǔ)形式式的實(shí)實(shí)例–mixturemodels（混合合模型型）,factoranalysis（因子子分析析）,hiddenMarkovmodels,Kalmanfilters（卡爾爾曼濾濾波器器）,etc.––在系統(tǒng)統(tǒng)工程程，信信息論論，模模式識(shí)識(shí)別和和統(tǒng)計(jì)計(jì)力學(xué)學(xué)中被被用到到?優(yōu)勢:––在某一一領(lǐng)域域中的的專業(yè)業(yè)技術(shù)術(shù)能夠夠在該該領(lǐng)域域中相相互轉(zhuǎn)轉(zhuǎn)化并并被充充分利利用–Providesnaturalframeworkfordesigningnewsystems圖模型型在機(jī)機(jī)器學(xué)學(xué)習(xí)中中的角角色形象化化概率率模型型結(jié)構(gòu)構(gòu)的簡簡單方方法InsightsintopropertiesofmodelConditionalindependencepropertiesbyinspectinggraph執(zhí)行推推理和和學(xué)習(xí)習(xí)表示示為圖圖形化化操作作需要要復(fù)雜雜的計(jì)計(jì)算圖的方方向性性?有向圖圖模型型–方向取取決于于箭頭頭?貝葉斯斯網(wǎng)絡(luò)絡(luò)–隨機(jī)變變量間間的因因果關(guān)關(guān)系?MorepopularinAIandstatistics?無向圖圖模型型–邊沒有有箭頭頭?Markovrandomfields（馬爾爾科夫夫隨機(jī)機(jī)場））–更適合合表達(dá)達(dá)變量量之間間的軟軟約束束?MorepopularinVisionandphysicsBayesiannetworks一種簡簡單的的，圖圖形化化的數(shù)數(shù)據(jù)結(jié)結(jié)構(gòu)，，用于于表示示變量量之間間的依依賴關(guān)關(guān)系系（條條件獨(dú)獨(dú)立性性），，為任任何全全聯(lián)合合概率率分布布提供供一種種簡明明的的規(guī)范范。Syntax語法:

asetofnodes,onepervariable

adirected（有向）,acyclic（無環(huán)）graph(link≈≈"directinfluences")

aconditionaldistributionforeachnodegivenitsparents:P(Xi|Parents(Xi))—量化其父節(jié)節(jié)點(diǎn)對(duì)該節(jié)節(jié)點(diǎn)的影響響Inthesimplestcase,conditionaldistributionrepresentedasaconditionalprobabilitytable條件概率表表(CPT)givingthedistributionoverXiforeachcombinationofparentvaluesExampleTopology（拓?fù)浣Y(jié)構(gòu)構(gòu)）ofnetworkencodesconditionalindependenceassertions:Weather獨(dú)立于其他他變量ToothacheandCatchareconditionallyindependentgivenCavityExample我晚上在單單位上班，，此時(shí)鄰居居John給我打電話話說我家警警報(bào)響了，，但是鄰居居Mary沒有給打電電話。有時(shí)時(shí)輕微的地地震也會(huì)引引起警報(bào)。。那么我家家真正遭賊賊了嗎？Variables:Burglary（入室行竊竊）,Earthquake,Alarm,JohnCalls,MaryCalls網(wǎng)絡(luò)拓?fù)浣Y(jié)結(jié)構(gòu)反映出出因果關(guān)系系:

–Aburglarcansetthealarmoff––Anearthquakecansetthealarmoff

–ThealarmcancauseMarytocall––ThealarmcancauseJohntocallExamplecontd.Compactness（緊致性））ACPTforBooleanXiwithkBooleanparentshas2krowsforthecombinationsofparentvalues一個(gè)具有k個(gè)布爾父節(jié)節(jié)點(diǎn)的布爾爾變量的條條件概率表表中有2k個(gè)獨(dú)立的可可指定概率率EachrowrequiresonenumberpforXi=true(thenumberforXi=falseisjust1-p)Ifeachvariablehasnomorethankparents,thecompletenetworkrequiresO(n··2k)numbersI.e.,growslinearlywithn,vs.O(2n)forthefulljointdistributionForburglarynet,1+1+4+2+2=10numbers(vs.25-1=31)Globalsemantics（全局語義義）Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:全聯(lián)合概率率分布可以以表示為貝貝葉斯網(wǎng)絡(luò)絡(luò)中的條件件概率分布布的乘積Globalsemantics（全局語義義）Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:全聯(lián)合概率率分布可以以表示為貝貝葉斯網(wǎng)絡(luò)絡(luò)中的條件件概率分布布的乘積LocalsemanticsLocalsemantics:eachnodeisconditionallyindependentofitsnondescendants（非后代））givenitsparents給定父節(jié)點(diǎn)點(diǎn)，一個(gè)節(jié)節(jié)點(diǎn)與它的的非后代節(jié)節(jié)點(diǎn)是條件件獨(dú)立的Theorem:LocalsemanticsglobalsemanticsCausalChains因果鏈一個(gè)基本形形式：–IsXindependentofZgivenY?–Evidencealongthechain““blocks””theinfluenceCommonCause共同原因另一個(gè)基礎(chǔ)礎(chǔ)的形態(tài):two

effectsofthesamecause––AreXandZindependent?

–AreXandZindependentgivenY?–Observingthecauseblocksinfluencebetweeneffects.CommonEffect共同影響最后一種配配置形態(tài):twocausesofoneeffect(v-structures)

–AreXandZindependent??Yes:remembertheballgameandtherain

causingtraffic,nocorrelation?–AreXandZindependentgivenY??No:rememberthatseeingtrafficputtherainandtheballgameincompetition?–Thisisbackwardsfromtheothercases?Observingtheeffectenablesinfluencebetweencauses.構(gòu)造貝葉葉斯網(wǎng)絡(luò)絡(luò)Needamethodsuchthataseriesoflocallytestableassertionsofconditionalindependenceguaranteestherequiredglobalsemantics需要一種種方法使使得局部部的條件件獨(dú)立關(guān)關(guān)系能夠夠保證全全局語義義得以成成立ChooseanorderingofvariablesX1,…,XnFori=1tonaddXitothenetworkselectparentsfromX1,…,Xi-1suchthatP(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)集對(duì)對(duì)每個(gè)變變量的那那些直接接影響。。添加節(jié)點(diǎn)點(diǎn)的正確確次序是是首先添添加“根根本原因因”節(jié)點(diǎn)點(diǎn)，然后后加入受受它們直直接影響響的變量量，以此此類推。。ExampleExampleExampleExampleExampleExamplecontd.在非因果果方向決決定條件件獨(dú)立性性是很難難的(Causalmodelsandconditionalindependenceseemhardwiredforhumans!)Networkislesscompact:1+2+4+2+4=13numbersneeded因果關(guān)系系??當(dāng)貝葉斯斯網(wǎng)絡(luò)反反映真正正的因果果模式時(shí)時(shí):

–Oftensimpler(nodeshavefewerparents)––Ofteneasiertothinkabout––Ofteneasiertoelicitfromexperts（專家））?BNs不一定必必須是因因果–有時(shí)無因因果關(guān)系系的網(wǎng)絡(luò)絡(luò)是存在在的(especiallyifvariablesaremissing)

–箭頭反映映相關(guān)性性，而不不是因果果關(guān)系?箭頭的真真正含義義是什么么?

–Topologymayhappentoencodecausalstructure––TopologyreallyencodesconditionalindependenceInferenceinBayesiannetworks推理任務(wù)務(wù)簡單查詢?cè)?計(jì)算后驗(yàn)驗(yàn)概率P(Xi|E=e)e.g.,P(NoGas|Gauge油表=empty,Lights=on,Starts=false)聯(lián)合查詢?cè)?P(Xi,Xj|E=e)=P(Xi|E=e)P(Xj|Xi,E=e)最優(yōu)決策策:decisionnetworksincludeutilityinformation;probabilisticinferencerequiredforP(outcome|action,evidence)通過枚舉舉進(jìn)行推推理上一章解解釋了任任何條件件概率都都可以通通過將全全聯(lián)合分分布表中中的某些些項(xiàng)相加加而計(jì)算算得到在貝葉斯斯網(wǎng)絡(luò)中中可以通通過計(jì)算算條件概概率的乘乘積并求求和來回回答查詢?cè)?。通過枚舉舉進(jìn)行推推理上一章解解釋了任任何條件件概率都都可以通通過將全全聯(lián)合分分布表中中的某些些項(xiàng)相加加而計(jì)算算得到Evaluationtree變量消元元法Variableelimination（變量消消元）:carryoutsummationsright-to-left,storingintermediateresults(factors：因子)toavoidrecomputation精確推理理的復(fù)雜雜度Singlyconnectednetworks單聯(lián)通網(wǎng)網(wǎng)絡(luò)(orpolytrees多樹):——anytwonodesareconnectedbyatmostone(undirected)path——timeandspacecostofvariableeliminationareO(dkn)多樹上的的變量消消元的時(shí)時(shí)間和空空間復(fù)雜雜度都與與網(wǎng)絡(luò)規(guī)規(guī)模呈線線性關(guān)系系。Multiplyconnectednetworks多聯(lián)通網(wǎng)網(wǎng)絡(luò):

—canreduce3SATtoexactinference??NP-hard——equivalenttocounting3SATmodels?#P-completeExample:Na?veBayesmodel單一父親親變量和和一批孩孩子變量量，孩子子變量在在給定父父親變量量下是相相互獨(dú)立立的Na?veBayesmodelTotalnumberofparameters（參數(shù)））islinearinnExample:垃圾郵件件檢測想象一下下試圖去去自動(dòng)檢檢測垃圾圾郵件的的問題.一個(gè)簡單單的方案案是只檢檢測主題題，然后后根據(jù)郵郵件的標(biāo)標(biāo)題檢查查一些簡簡單的特特征來嘗嘗試識(shí)別別垃圾郵郵件.我們先考考慮兩個(gè)個(gè)簡單的的特征:Caps:是否標(biāo)題題是徹底底大寫的的Free:是否標(biāo)題題中包含含大寫或或小寫的的單詞‘‘free’e.g.:amessagewiththesubjectheader““NEWMORTGAGERATE“islikelytobespam.Similarly,for““MoneyforFree”,““FREElunch””,etc.Example:垃圾郵件件檢測模型的構(gòu)構(gòu)建基于于以下三三個(gè)隨機(jī)機(jī)變量,Caps,FreeandSpam,eachofwhichtakeonthevaluesY(forYes)orN(forNo)Caps=YifandonlyifthesubjectofthemessagedoesnotcontainlowercaselettersFree=Yifandonlyiftheword`free'appearsinthesubject(lettercaseisignored)Spam=YifandonlyifthemessageisspamP(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:Learningtoclassifytext

documents文本分類類是在文文檔所包包含的文文本基礎(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)確地解解釋如何何對(duì)新文文檔進(jìn)行行分類。。c.這里獨(dú)立立性假設(shè)設(shè)合理嗎嗎？請(qǐng)討討論。Example:Learningtoclassifytext

documents模型包含含先驗(yàn)概概率P(Category)和條件概率P(wordi|Category)?P(Category=c)isestimatedasthefractionofalldocumentsthatareofcategoryc?P(wordi=true|Category=c)isestimatedasthefractionofdocumentsofcategorycthatcontainwordiTwentyNewsgroupsGiven1000trainingdocumentsfromeachgroup.Learntoclassifynewdocumentsaccordingtowhichnewsgroupitca