Bayesiannetworks

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

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

但是，在許多情景下不可能進(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可以通過(guò)把對(duì)應(yīng)于查詢命題的原子事件的條目相加的方式來(lái)回答查詢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è)簡(jiǎn)單線性方程來(lái)表達(dá)–SumRule（加法規(guī)則）?變量的概率是通過(guò)邊緣化或者求和其他變量獲得的–ProductRule（乘法規(guī)則）?用條件表達(dá)聯(lián)合概率所有的概率推理和學(xué)習(xí)相當(dāng)于不斷重復(fù)加法和乘法法則大綱Graphicalmodels（概率圖模型）Bayesiannetworks

–Syntax（語(yǔ)法）

–Semantics（語(yǔ)義）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è)部分連接起來(lái),確保系統(tǒng)作為一個(gè)整體是一致的

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

–直觀的接口

?bywhichhumanscanmodelhighly-interactingsetsofvariables

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

?thatlendsitselfnaturallytodesigningefficientgeneral-purpose（通用的）algorithmsGraphicalmodels:統(tǒng)一的框架?考慮傳統(tǒng)的多變量的概率系統(tǒng)作為一般基礎(chǔ)形式的實(shí)例

–mixturemodels（混合模型）,factoranalysis（因子分析）,hiddenMarkovmodels,Kalmanfilters（卡爾曼濾波器）,etc.

–在系統(tǒng)工程，信息論，模式識(shí)別和統(tǒng)計(jì)力學(xué)中被用到?優(yōu)勢(shì):

–在某一領(lǐng)域中的專業(yè)技術(shù)能夠在該領(lǐng)域中相互轉(zhuǎn)化并被充分利用

–Providesnaturalframeworkfordesigningnewsystems圖模型在機(jī)器學(xué)習(xí)中的角色形象化概率模型結(jié)構(gòu)的簡(jiǎn)單方法Insightsintopropertiesofmodel

Conditionalindependencepropertiesbyinspectinggraph執(zhí)行推理和學(xué)習(xí)表示為圖形化操作需要復(fù)雜的計(jì)算圖的方向性?有向圖模型

–方向取決于箭頭?貝葉斯網(wǎng)絡(luò)

–隨機(jī)變量間的因果關(guān)系?MorepopularinAIand

statistics?無(wú)向圖模型

–邊沒(méi)有箭頭?Markovrandomfields

（馬爾科夫隨機(jī)場(chǎng)）

–更適合表達(dá)變量之間的軟約束?MorepopularinVisionandphysicsBayesiannetworks一種簡(jiǎn)單的，圖形化的數(shù)據(jù)結(jié)構(gòu)，用于表示變量之間的依賴

關(guān)系（條件獨(dú)立性），為任何全聯(lián)合概率分布提供一種簡(jiǎn)

明的規(guī)范。Syntax語(yǔ)法:

asetofnodes,onepervariable

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

aconditionaldistributionforeachnodegivenitsparents:

P(Xi|Parents(Xi))—量化其父節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的影響Inthesimplestcase,conditionaldistributionrepresentedasa

conditionalprobabilitytable條件概率表(CPT)givingthe

distributionoverXi

foreachcombinationofparentvaluesExampleTopology（拓?fù)浣Y(jié)構(gòu)）ofnetworkencodesconditionalindependenceassertions:

Weather獨(dú)立于其他變量

ToothacheandCatchareconditionallyindependentgivenCavityExample我晚上在單位上班，此時(shí)鄰居John給我打電話說(shuō)我家警報(bào)響了，但是鄰居Mary沒(méi)有給打電話。有時(shí)輕微的地震也會(huì)引起警報(bào)。那么我家真正遭賊了嗎？Variables:Burglary（入室行竊）,Earthquake,Alarm,JohnCalls,MaryCalls網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)反映出因果關(guān)系:

–Aburglarcansetthealarmoff

–Anearthquakecansetthealarmoff

–ThealarmcancauseMarytocall

–ThealarmcancauseJohntocallExamplecontd.Compactness（緊致性）ACPTforBooleanXiwithkBooleanparentshas2k

rowsforthecombinationsofparentvalues一個(gè)具有k個(gè)布爾父節(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（全局語(yǔ)義）Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:

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

全聯(lián)合概率分布可以表示為貝葉斯網(wǎng)絡(luò)中的條件概率分布的乘積LocalsemanticsLocalsemantics:eachnodeisconditionallyindependentofitsnondescendants（非后代）givenitsparents給定父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)與它的非后代節(jié)點(diǎn)是條件獨(dú)立的Theorem:LocalsemanticsglobalsemanticsCausalChains因果鏈一個(gè)基本形式：–IsXindependentofZgivenY?

–Evidencealongthechain“blocks”theinfluenceCommonCause共同原因另一個(gè)基礎(chǔ)的形態(tài):two

effectsofthesamecause

–AreXandZindependent?

–AreXandZindependentgivenY?–Observingthecauseblocksinfluence

betweeneffects.CommonEffect共同影響最后一種配置形態(tài):twocausesofone

effect(v-structures)

–AreXandZindependent?

?Yes:remembertheballgameandtherain

causingtraffic,nocorrelation?

–AreXandZindependentgivenY?

?No:rememberthatseeingtrafficputtherain

andtheballgameincompetition?

–Thisisbackwardsfromtheothercases

?Observingtheeffectenablesinfluencebetween causes.構(gòu)造貝葉斯網(wǎng)絡(luò)Needamethodsuchthataseriesoflocallytestableassertionsofconditionalindependenceguaranteestherequiredglobalsemantics需要一種方法使得局部的條件獨(dú)立關(guān)系能夠保證全局語(yǔ)義得以成立ChooseanorderingofvariablesX1,…,XnFori=1ton

addXi

tothenetwork

selectparentsfromX1,…,Xi-1

suchthat

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

(Causalmodelsandconditionalindependenceseemhardwiredforhumans!)

Networkislesscompact:1+2+4+2+4=13numbersneeded因果關(guān)系??當(dāng)貝葉斯網(wǎng)絡(luò)反映真正的因果模式時(shí):

–Oftensimpler(nodeshavefewerparents)

–Ofteneasiertothinkabout

–Ofteneasiertoelicitfromexperts（專家）?BNs不一定必須是因果

–有時(shí)無(wú)因果關(guān)系的網(wǎng)絡(luò)是存在的(especiallyifvariablesaremissing)

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

–Topologymayhappentoencodecausalstructure

–TopologyreallyencodesconditionalindependenceInferenceinBayesiannetworks推理任務(wù)簡(jiǎn)單查詢:計(jì)算后驗(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)決策:decisionnetworksincludeutilityinformation;probabilisticinferencerequiredfor

P(outcome|action,evidence)通過(guò)枚舉進(jìn)行推理上一章解釋了任何條件概率都可以通過(guò)將全聯(lián)合分布表中的某些項(xiàng)相加而計(jì)算得到在貝葉斯網(wǎng)絡(luò)中可以通過(guò)計(jì)算條件概率的乘積并求和來(lái)回答查詢。通過(guò)枚舉進(jìn)行推理上一章解釋了任何條件概率都可以通過(guò)將全聯(lián)合分布表中的某些項(xiàng)相加而計(jì)算得到Evaluationtree變量消元法Variableelimination（變量消元）:carryoutsummationsright-to-left,storingintermediateresults(factors：因子)toavoidrecomputation精確推理的復(fù)雜度Singlyconnectednetworks單聯(lián)通網(wǎng)絡(luò)(orpolytrees多樹(shù)):

—anytwonodesareconnectedbyatmostone(undirected)path

—timeandspacecostofvariableeliminationareO(dkn)

多樹(shù)上的變量消元的時(shí)間和空間復(fù)雜度都與網(wǎng)絡(luò)規(guī)模呈線性關(guān)系。Multiplyconnectednetworks多聯(lián)通網(wǎng)絡(luò):

—canreduce3SATtoexactinference?NP-hard

—equivalenttocounting3SATmodels?#P-completeExample:Na?veBayesmodel單一父親變量和一批孩子變量，孩子變量在給定父親變量下是相互獨(dú)立的

Na?veBayesmodelTotalnumberofparameters（參數(shù)）islinearinn

Example:垃圾郵件檢測(cè)想象一下試圖去自動(dòng)檢測(cè)垃圾郵件的問(wèn)題.一個(gè)簡(jiǎn)單的方案是只檢測(cè)主題，然后根據(jù)郵件的標(biāo)題檢查一些簡(jiǎn)單的特征來(lái)嘗試識(shí)別垃圾郵件.我們先考慮兩個(gè)簡(jiǎn)單的特征:

Caps:是否標(biāo)題是徹底大寫(xiě)的Free:是否標(biāo)題中包含大寫(xiě)或小寫(xiě)的單詞‘free’

e.g.:amessagewiththesubjectheader“NEWMORTGAGERATE“islikelytobespam.Similarly,for“MoneyforFree”,“FREElunch”,etc.Example:垃圾郵件檢測(cè)模型的構(gòu)建基于以下三個(gè)隨機(jī)變量,

Caps,FreeandSpam,eachofwhichtakeonthevaluesY(forYes)orN(forNo)Caps=Yifandonlyifthesubjectofthemessagedoesnot

containlowercaselettersFree=Yifandonlyiftheword`free'appearsinthesubject

(lettercaseisignored)Spam=YifandonlyifthemessageisspamP(Free,Caps,Spam)=P(Spam)P(Caps|Spam)P(Free|Spam)Example:垃圾郵件檢測(cè)P(Free,Caps,Spam)=P(Spam)P(Caps|Spam)P(Free|Spam)

Example:垃圾郵件檢測(cè)Example:垃圾郵件檢測(cè)Example:Learningtoclassifytext

documents文本分類是在文檔所包含的文本基礎(chǔ)上，把給定的文檔分配

到固定類別集合中某一個(gè)類別的任務(wù)。這個(gè)任務(wù)中常常用

到樸素貝葉斯模型。在這些模型中，查詢變量是文檔類別

，“結(jié)果”變量則是語(yǔ)言中每個(gè)詞是否出現(xiàn)。我們假設(shè)文

檔中的詞的出現(xiàn)都是獨(dú)立的，其出現(xiàn)頻率由文檔類別確定

。

a.準(zhǔn)確地解釋當(dāng)給定一組類別已經(jīng)確定的文檔作為“訓(xùn)練數(shù)據(jù)”時(shí)，這樣的模型是如何構(gòu)造的。

b.準(zhǔn)確地解釋如何對(duì)新文檔進(jìn)行分類。

c.這里獨(dú)立性假設(shè)合理嗎？請(qǐng)討論。Example:Learningtoclassifytext

documents模型包含先驗(yàn)概率P(Category)和

條件概率P(wordi|Category)?P(Category=c)isestimatedasthefractionofalldocumentsthatareofcategoryc?P(wordi=true|Category=c)isestimatedasthefractionofdocumentsofcategorycthatcontainwordiTwentyNewsgroupsGiven1000trainingdocumentsfromeachgroup.Learntoclassifynewdocumentsaccordingtowhichnewsgroupitcamefrom

Na?veBayes:89%classificationaccuracyLearningCurvefor20NewsgroupsExample:ADigitRe