人工智能08不確定性課件

手寫數(shù)字識別手寫數(shù)字識別1文本分類文本分類2圖像分割圖像分割3第八章Uncertainty

不確定性對應(yīng)教材第13章第八章Uncertainty

不確定性對應(yīng)教材第13章4本章大綱Uncertainty不確定性Probability概率SyntaxandSemantics語法與語義Inference推理IndependenceandBayes‘Rule

—獨(dú)立性及貝葉斯法則

本章大綱Uncertainty不確定性5不確定性智能體幾乎從來無法了解關(guān)于其環(huán)境的全部事實(shí)。因此其必須在不確定的環(huán)境下行動。概率推理

得到了某一證據(jù)，那么有多大的幾率結(jié)論為真？

例如：我頸部痛;我得腦膜炎的可能有多大?不確定性智能體幾乎從來無法了解關(guān)于其環(huán)境的全部事實(shí)。因此其必6不確定性假如有如下規(guī)則:

iftoothache（牙疼）then原因是cavity（牙齒有洞）但并不是所有牙疼的病人都是因?yàn)檠例X有洞，所以我們可以建立如下規(guī)則:

iftoothacheand?gum-disease（牙齦疾?。゛nd

?filling（補(bǔ)牙）and...thenproblem=cavity以上規(guī)則是復(fù)雜的;更好的方法:

iftoothachethenproblemiscavitywith0.8probability

orP(cavity|toothache)=0.8

theprobabilityofcavityis0.8giventoothacheisobserved不確定性假如有如下規(guī)則:

iftoothache（牙疼）7不確定性 LetactionAt=離起飛時間提前t分鐘動身去機(jī)場

At會使我準(zhǔn)時到達(dá)機(jī)場嗎?

Problems:

1.partialobservability/部分可觀察性(roadstate,otherdrivers‘plans)

2.noisysensors(trafficreports)

3.行動結(jié)果的不確定性(flattire,etc.)

4.immensecomplexityofmodelingandpredictingtraffic

因此一個純粹的邏輯描述方法：

1.risksfalsehood（錯誤風(fēng)險）:“A25

willgetmethereontime”,or

2.leadstoconclusionsthataretooweakfordecisionmaking:

“A25

willgetmethereontimeifthere’snoaccidentonthebridgeanditdoesn‘trainandmytiresremainintactetcetc.”

(A1440

mightreasonablybesaidtogetmethereontimebutI’dhavetostayovernightintheairport…)不確定性 LetactionAt=離起飛時間提前t分8世界與模型中的不確定性Trueuncertainty:rulesareprobabilisticinnature

擲骰子，拋硬幣惰性:把所有意外的規(guī)則都列舉出來是很困難的

花費(fèi)太多時間來確定所有的相關(guān)因素

這些規(guī)則過于繁雜而難以使用理論的無知:某些領(lǐng)域中還沒有完整的理論

(e.g.,medicaldiagnosis)實(shí)踐的無知:掌握了所有規(guī)則但是

并不是所有的相關(guān)信息都能被收集到世界與模型中的不確定性Trueuncertainty:r9處理不確定性的方法概率理論作為一種正式的方法for：

不確定知識的表示和推理

命題中的模型信度(event,conclusion,diagnosis,etc.)

給定可獲得的證據(jù),

A25

willgetmethereontimewithprobability0.04概率是不確定性的語言

現(xiàn)代AI的中心支柱處理不確定性的方法概率理論作為一種正式的方法for：

不確定10Probability概率概率理論提供了一種方法以概括來自我們的惰性和無知的不確定性。Probabilisticassertionssummarizeeffectsof

Laziness（惰性）:failuretoenumerateexceptions（例外）,qualifications（條件）,etc.

Ignorance（理論的無知）:lackofrelevantfacts,initialconditions,etc.Subjectiveprobability（主觀概率）:

Probabilitiesrelatepropositions（命題）toagent'sownstateof

knowledge

e.g.,P(A25|noreportedaccidents)=0.06Thesearenotassertions（斷言）abouttheworld命題的概率隨著新證據(jù)的發(fā)現(xiàn)而改變:

e.g.,P(A25|noreportedaccidents,5a.m.)=0.15Probability概率概率理論提供了一種方法以概括來自我11不確定條件下的決策假設(shè)下述概率是真的:

P(A25getsmethereontime|…)=0.04

P(A90getsmethereontime|…)=0.70

P(A120getsmethereontime|…)=0.95

P(A1440getsmethereontime|…)=0.9999Whichactiontochoose?

Dependsonmypreferences（偏好）formissingflightvs.time

spentwaiting,etc.

Utilitytheory（效用理論）用來對偏好進(jìn)行表示和推理

Decisiontheory=probabilitytheory+utilitytheory

決策理論=概率理論+效用理論不確定條件下的決策假設(shè)下述概率是真的:12Syntax語法基本元素:randomvariable（隨機(jī)變量）

Arandomvariableissomeaspectoftheworldaboutwhichwe(may)haveuncertainty

通常大寫e.g.,Cavity,Weather,Temperature類似于命題邏輯:未知世界被隨機(jī)變量的賦值所定義Booleanrandomvariables（布爾隨機(jī)變量）

e.g.,Cavity（牙洞）(doIhaveacavity?)Discreterandomvariables（離散隨機(jī)變量）

e.g.,Weatherisoneof<sunny,rainy,cloudy,snow>定義域mustbeexhaustive（窮盡的）andmutuallyexclusive（互斥的）Continuousrandomvariables（連續(xù)隨機(jī)變量）

e.g.,Temp=21.6;alsoallow,e.g.,Temp<22.0Syntax語法基本元素:randomvariable（13SyntaxElementaryproposition（命題）constructedbyassignmentofavaluetoarandomvariable:e.g.,Weather=sunny,Cavity=false

(簡寫為?cavity)Complexpropositionsformedfromelementarypropositionsandstandardlogicalconnectivese.g.,Weather=sunny∨Cavity=falseSyntaxElementaryproposition（命14SyntaxAtomicevent:Acompletespecificationofthestateof

theworldaboutwhichtheagentisuncertain原子事件：對智能體無法確定的世界狀態(tài)的一個完

整的詳細(xì)描述。E.g.,iftheworldconsistsofonlytwoBooleanvariablesCavity

andToothache,thenthereare4distinctatomicevents:

Cavity=false∧Toothache=false

Cavity=false∧Toothache=true

Cavity=true∧Toothache=false

Cavity=true∧Toothache=true

Atomiceventsaremutuallyexclusiveandexhaustive

窮盡和互斥SyntaxAtomicevent:Acomplete15概率公理對任意命題A,B

0≤P(A)≤1

P(true)=1andP(false)=0

P(A∨B)=P(A)+P(B)-P(A∧B)

概率公理對任意命題A,B

0≤P(A)≤1

P16Priorprobability（先驗(yàn)概率）Priororunconditionalprobabilities（無條件概率）ofpropositions在沒有任何其它信息存在的情況下關(guān)于命題的信度

e.g.,P(Cavity=true)=0.1andP(Weather=sunny)=0.72correspondtobeliefpriortoarrivalofany(new)evidenceProbabilitydistributiongivesvaluesforallpossibleassignments:概率分布給出一個隨機(jī)變量所有可能取值的概率

P(Weather)=<0.72,0.1,0.08,0.1>(normalized（歸一化的）,i.e.,sumsto1)Jointprobabilitydistributionforasetofrandomvariablesgivestheprobabilityofeveryatomiceventonthoserandomvariables(i.e.,everysamplepoint)聯(lián)合概率分布給出一個隨機(jī)變量集的值的全部組合的概率

P(Weather,Cavity)=a4×2matrixofvalues:EveryquestionaboutadomaincanbeansweredbythejointdistributionbecauseeveryeventisasumofsamplepointsPriorprobability（先驗(yàn)概率）Prioro17連續(xù)變量的概率Expressdistributionasaparameterized（參數(shù)化的）functionofvalue:P(X=x)=U[18,26](x)=uniform（均勻分布）densitybetween18and26連續(xù)變量的概率Expressdistributionas18連續(xù)變量的概率連續(xù)變量的概率19MarginalDistributions（邊緣概率分布）Marginaldistributionsaresub-tableswhicheliminatevariablesMarginalization(summingout):CombinecollapsedrowsbyaddingMarginalDistributions（邊緣概率分布）20Conditionalprobability（條件概率）Conditionalorposteriorprobabilities（后驗(yàn)概率）P(a|b)

證據(jù)累積過程的形式化和發(fā)現(xiàn)新證據(jù)后的概率更新

當(dāng)一個命題為真的條件下，指定命題的概率

e.g.,P(cavity|toothache)=0.8

i.e.,鑒于牙疼是已知證據(jù)

(Notationforconditionaldistributions（條件概率分布）:

P(cavity|toothache)=asinglenumber

P(Cavity,Toothache)=2x2tablesummingto1

P(Cavity|Toothache)=2-elementvectorof2-elementvectorsIfweknowmore,e.g.,cavityisalsogiven,thenwehave

P(cavity|toothache,cavity)=1

新證據(jù)可能是不相關(guān)的，可以簡化,e.g.,

P(cavity|toothache,sunny)=P(cavity|toothache)=0.8Conditionalprobability（條件概率）C21條件概率定義條件概率為:

P(a|b)=P(a∧b)/P(b)ifP(b)>0Productrule（乘法規(guī)則）

givesanalternativeformulation:

P(a∧b)=P(a|b)P(b)=P(b|a)P(a)Ageneralversionholdsforwholedistributions,e.g.,

P(Weather,Cavity)=P(Weather|Cavity)P(Cavity)(Viewasasetof4×2equations,notmatrixmultiplication)Chainrule（鏈?zhǔn)椒▌t）isderivedbysuccessiveapplicationofproductrule:條件概率定義條件概率為:

P(a|b)=P(a∧22條件概率條件概率跟標(biāo)準(zhǔn)概率一樣,forexample:

0<=P(a|e)<=1

conditionalprobabilitiesarebetween0and1inclusive

P(a1|e)+P(a2|e)+...+P(ak|e)=1

conditionalprobabilitiessumto1wherea1,…,ak

areallvaluesinthedomainofrandomvariableA

P(?a|e)=1-P(a|e)

negationforconditionalprobabilities條件概率條件概率跟標(biāo)準(zhǔn)概率一樣,forexample:

23通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:Foranypropositionφ,sumtheatomiceventswhereitistrue:一個命題的概率等于所有當(dāng)它為真時的原子事件的概率和

通過枚舉的推理Startwiththejointpr24通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:Foranypropositionφ,sumtheatomiceventswhereitistrue:一個命題的概率等于所有當(dāng)它為真時的原子事件的概率和

通過枚舉的推理Startwiththejointpr25通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:Foranypropositionφ,sumtheatomiceventswhereitistrue:一個命題的概率等于所有當(dāng)它為真時的原子事件的概率和

通過枚舉的推理Startwiththejointpr26通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:通過枚舉的推理Startwiththejointpr27Normalization（歸一化）Denominator（分母）canbeviewedasanormalizationconstantα

P(Cavity|toothache)=αP(Cavity,toothache)

=α[P(Cavity,toothache,catch)+P(Cavity,toothache,?catch)]

=α[<0.108,0.016>+<0.012,0.064>]

=α<0.12,0.08>=<0.6,0.4>

Generalidea:computedistributiononqueryvariablebyfixing

evidencevariables（證據(jù)變量）andsummingoverhidden

variables（未觀測變量）Normalization（歸一化）Denominator（28通過枚舉的推理Typically,weareinterestedin

theposteriorjointdistributionofthequeryvariables（查詢變量）Y

givenspecificvaluesefortheevidencevariables（證據(jù)變量）ELetthehiddenvariables（未觀測變量）beH=X-Y–EThentherequiredsummationofjointentriesisdonebysummingoutthehiddenvariables:

P(Y|E=e)=αP(Y,E=e)=αΣhP(Y,E=e,H=h)ThetermsinthesummationarejointentriesbecauseY,EandHtogetherexhaustthesetofrandomvariables（Y,E,H構(gòu)成了域中所有變量的完整集合）Obviousproblems:

1.Worst-casetimecomplexityO(dn)wheredisthelargestarity

2.SpacecomplexityO(dn)tostorethejointdistribution

3.HowtofindthenumbersforO(dn)entries?通過枚舉的推理Typically,weareinter29Independence（獨(dú)立性）AandBareindependentiff

P(A|B)=P(A)orP(B|A)=P(B)orP(A,B)=P(A)P(B)E.g:rollof2die:P({1},{3})=1/6*1/6=1/36P(Toothache,Catch,Cavity,Weather)=P(Toothache,Catch,Cavity)P(Weather)32entriesreducedto12;fornindependentbiasedcoins,O(2n)→O(n)Absoluteindependencepowerfulbutrare絕對獨(dú)立強(qiáng)大但罕見Dentistry（牙科領(lǐng)域）isalargefieldwithhundredsofvariables,noneofwhichareindependent.Whattodo?Independence（獨(dú)立性）AandBarei30獨(dú)立的濫用天真的數(shù)學(xué)笑話：一個著名統(tǒng)計學(xué)家永遠(yuǎn)不會坐飛機(jī)旅行,因?yàn)樗芯苛撕娇章眯泻凸烙?任何給定的航班上有炸彈的可能性是一百萬分之一,他不準(zhǔn)備接受這些可能性。有一天，一位同時在遠(yuǎn)離家鄉(xiāng)的會議上遇到他。“你怎么到這里的？坐火車嗎？”“不，我飛過來的”“Whataboutthepossibilityofabomb?”“Well,Ibeganthinkingthatiftheoddsofonebombare1:million,thentheoddsoftwobombsare(1/1,000,000)x(1/1,000,000).Thisisavery,verysmallprobability,whichIcanaccept.SonowIbringmyownbombalong!”獨(dú)立的濫用天真的數(shù)學(xué)笑話：31Conditionalindependence

條件獨(dú)立性Randomvariablescanbedependent,butconditionally

independent

Example:Yourhousehasanalarm

NeighborJohnwillcallwhenhehearsthealarm

NeighborMarywillcallwhenshehearsthealarm

AssumeJohnandMarydon’ttalktoeachother

IsJohnCallindependentofMaryCall?

No–IfJohncalled,itislikelythealarmwentoff,whichincreasestheprobabilityofMarycalling

P(MaryCall|JohnCall)≠P(MaryCall)Conditionalindependence

條件獨(dú)立性32條件獨(dú)立性But,ifweknowthestatusofthealarm,JohnCallwillnot

affectwhetherornotMarycalls

P(MaryCall|Alarm,JohnCall)=P(MaryCall|Alarm)

WesayJohnCallandMaryCallareconditionally

independentgivenAlarm

Ingeneral,“AandBareconditionallyindependentgivenC”

means:

P(A|B,C)=P(A|C)

P(B|A,C)=P(B|C)

P(A,B|C)=P(A|C)P(B|C)條件獨(dú)立性But,ifweknowthestatu33條件獨(dú)立性P(Toothache,Cavity,Catch)has23-1=7independententries專業(yè)領(lǐng)域知識:Cavitydirectlycausestoothacheandprobe-catches.IfIhave

acavity,theprobabilitythattheprobecatchesinitdoesn‘tdependonwhether

Ihaveatoothache:

(1)P(catch|toothache,cavity)=P(catch|cavity)ThesameindependenceholdsifIhaven’tgotacavity:

(2)P(catch|toothache,?cavity)=P(catch|?cavity)CatchisconditionallyindependentofToothachegivenCavity:

P(Catch|Toothache,Cavity)=P(Catch|Cavity)Equivalentstatements:

P(Toothache|Catch,Cavity)=P(Toothache|Cavity)

P(Toothache,Catch|Cavity)=P(Toothache|Cavity)P(Catch|Cavity)條件獨(dú)立性P(Toothache,Cavity,Catc34條件獨(dú)立性Writeoutfulljointdistributionusingchainrule:

P(Toothache,Catch,Cavity)

=P(Toothache|Catch,Cavity)P(Catch,Cavity)

=P(Toothache|Catch,Cavity)P(Catch|Cavity)P(Cavity)

=P(Toothache|Cavity)P(Catch|Cavity)P(Cavity)

I.e.,2+2+1=5independentnumbersInmostcases,theuseofconditionalindependencereducesthesizeofthe

representationofthejointdistributionfromexponentialinntolinearinn.在大多數(shù)情況下，使用條件獨(dú)立性能將全聯(lián)合概率的表示由n的指數(shù)關(guān)系減為n的線性關(guān)系。Conditionalindependenceisourmostbasicandrobustformofknowledgeaboutuncertainenvironments.條件獨(dú)立性Writeoutfulljointdist35Bayes’Rule（貝葉斯法則）Bayes’Rule（貝葉斯法則）36Bayes’Rule（貝葉斯法則）乘法原則?Bayes‘rule:orindistributionform

為什么該法則非常有用?

將條件倒轉(zhuǎn)

通常一個條件是復(fù)雜的，一個是簡單的

許多系統(tǒng)的基礎(chǔ)(e.g.語音識別)現(xiàn)代AI基礎(chǔ)！Bayes’Rule（貝葉斯法則）乘法原則37Bayes’Rule（貝葉斯法則）Usefulforassessingdiagnosticprobability（診斷概率）fromcausalprobability（因果概率）:E.g.,letMbemeningitis（腦膜炎）,Sbestiffneck（脖子僵硬）:Note:腦膜炎的后驗(yàn)概率依然非常小!Note:依然要先檢測脖子僵硬!Why?Bayes’Rule（貝葉斯法則）38Bayes’RuleinPracticeBayes’RuleinPractice39使用貝葉斯法則:IH=“havingaheadache“頭痛F=“comingdownwithFlu”流感

P(H)=1/10

P(F)=1/40

P(H|F)=1/2有一天你早上醒來發(fā)現(xiàn)頭很痛，于是得到以下結(jié)論：“因?yàn)榈昧肆鞲幸院?0%的幾率會引起頭痛，所以我有50%的幾率得了流感”Isthisreasoningcorrect?使用貝葉斯法則:IH=“havingaheadac40使用貝葉斯法則:IH="havingaheadache“F="comingdownwithFlu"

P(H)=1/10

P(F)=1/40

P(H|F)=1/2TheProblem:

P(F|H)=?

使用貝葉斯法則:IH="havingaheadac41使用貝葉斯法則:IH="havingaheadache“F="comingdownwithFlu"

P(H)=1/10

P(F)=1/40

P(H|F)=1/2TheProblem:

P(F|H)=P(H|F)P(F)/P(H)

=1/8≠P(H|F)

使用貝葉斯法則:IH="havingaheadac42使用貝葉斯法則:II在一個包裹里有2個信封

一個信封里有一個紅球(worth$100)和一個黑球

另一個信封里有2個黑球.黑球一文不值然后你隨機(jī)拿出一個信封，并隨機(jī)拿出一個球 –it’sblack此時此刻給你個機(jī)會換一個信封.是換呢還是換呢還是換呢?使用貝葉斯法則:II在一個包裹里有2個信封

一個信43使用貝葉斯法則:IIE:envelope,1=(R,B),2=(B,B)B:theeventofdrawingablackball

P(E|B)=P(B|E)*P(E)/P(B)WewanttocompareP(E=1|B)vs.P(E=2|B)

P(B|E=1)=0.5,P(B|E=2)=1

P(E=1)=P(E=2)=0.5

P(B)=P(B|E=1)P(E=1)+P(B|E=2)P(E=2)=(.5)(.5)+(1)(.5)=.75

P(E=1|B)=P(B|E=1)P(E=1)/P(B)=(.5)(.5)/(.75)=1/3

P(E=2|B)=P(B|E=2)P(E=2)/P(B)=(1)(.5)/(.75)=2/3因此在已發(fā)現(xiàn)一個黑球后,該信封是1的后驗(yàn)概率(thusworth$100)比信封是2的后驗(yàn)概率低

所以還是換吧使用貝葉斯法則:IIE:envelope,1=(R,B44課堂測驗(yàn)一名醫(yī)生做了一個具有99%可靠性的測試：也就是說,99%的病人其檢測呈陽性,99%的健康人士檢測呈陰性.該醫(yī)生估計1%的人類病了。。。

Question:一個患者檢測呈陽性.該患者得病的幾率是多少?

0-25%,25-75%,75-95%,or95-100%?

課堂測驗(yàn)一名醫(yī)生做了一個具有99%可靠性的測試：也就是說,45課堂測驗(yàn)Adoctorperformsatestthathas99%reliability,i.e.,99%of

peoplewhoaresicktestpositive,and99%ofpeoplewhoarehealthytestnegative.Thedoctorestimatesthat1%ofthepopulationissick.

Question:Apatienttestspositive.Whatisthechancethatthepatientissick?

0-25%,25-75%,75-95%,or95-100%?

Intuitiveanswer:99%;Correctanswer:50%課堂測驗(yàn)Adoctorperformsatestt46Bayes’rulewith多重證據(jù)和條件獨(dú)立性P(Cavity|toothache∧catch)

=αP(toothache∧catch|Cavity)P(Cavity)

=αP(toothache|Cavity)P(catch|Cavity)P(Cavity)Thisisanexampleofana?veBayesmodel（樸素貝葉斯模型）:Totalnumberofparameters（參數(shù)）islinearinnBayes’rulewith多重證據(jù)和條件獨(dú)立性P(C47鏈?zhǔn)椒▌t全聯(lián)合分布using鏈?zhǔn)椒▌t:

P(Toothache,Catch,Cavity)

=P(Toothache|Catch,Cavity)P(Catch,Cavity)

=P(Toothache|Catch,Cavity)P(Catch|Cavity)P(Cavity)

=P(Toothache|Cavity)P(Catch|Cavity)P(Cavity)圖模型:

?Eachvariableisanode

?Theparentsofanodearethe

othervariableswhichthe

decomposedjointconditionson

?MUCHmoreonthistocome!鏈?zhǔn)椒▌t全聯(lián)合分布using鏈?zhǔn)椒▌t:

P(Tootha48概率分布從哪來?IdeaOne:人類,領(lǐng)域?qū)＜?/p>

E.g.what’sP(raining|cold)?

IdeaTwo:簡單事實(shí)和一些代數(shù)學(xué)

使用鏈?zhǔn)椒▌t和獨(dú)立性來試著計算聯(lián)合分布概率分布從哪來?IdeaOne:人類,領(lǐng)域?qū)＜?/p>

E49概率分布從哪來?IdeaThree:從數(shù)據(jù)里學(xué)習(xí)出來的!

Agoodchunkofmachinelearningresearchisessentiallyaboutvariouswaysoflearningvariousformsofthem!

概率分布從哪來?IdeaThree:從數(shù)據(jù)里學(xué)習(xí)出來的!50Estimation估計怎樣去估計一個隨機(jī)變量X的分布?

Maximumlikelihood（最大似然）:

從現(xiàn)實(shí)世界中收集觀察值

Foreachvaluex,lookattheempiricalrateofthatvalue:

ThisestimateistheonewhichmaximizesthelikelihoodofthedataEstimation估計怎樣去估計一個隨機(jī)變量X的分布?

51Estimation估計Problemswith最大似然估計:

如果我拋一次硬幣,是正面heads,那么對P(heads)的估計是多少?

WhatifIflipit50timeswith27heads?

WhatifIflip10Mtimeswith8Mheads?

Basicidea:

我們對一些參數(shù)有先驗(yàn)期望值(here,theprobabilityofheads)

在缺少證據(jù)時，我們傾向先驗(yàn)值

若給定很多證據(jù),則應(yīng)該以數(shù)據(jù)為準(zhǔn)Estimation估計Problemswith最大似然52SummaryProbabilityisarigorousformalismforuncertainknowledge概率是對不確定知識一種嚴(yán)密的形式化方法Jointprobabilitydistributionspecifiesprobabilityofeveryatomicevent全聯(lián)合概率分布指定了對隨機(jī)變量的每種完全賦值，即每個原子事件的概率Queriescanbeansweredbysummingoveratomicevents可以通過把對應(yīng)于查詢命題的原子事件的條目相加的方式來回答查詢Fornontrivialdomains,wemustfindawaytoreducethejointsizeIndependenceandconditionalindependenceprovidethetoolsSummaryProbabilityisarigoro53作業(yè)13.8，13.11，13.16，13.18(不交)

作業(yè)13.8，13.11，13.16，13.18(不54手寫數(shù)字識別手寫數(shù)字識別55文本分類文本分類56圖像分割圖像分割57第八章Uncertainty

不確定性對應(yīng)教材第13章第八章Uncertainty

不確定性對應(yīng)教材第13章58本章大綱Uncertainty不確定性Probability概率SyntaxandSemantics語法與語義Inference推理IndependenceandBayes‘Rule

—獨(dú)立性及貝葉斯法則

本章大綱Uncertainty不確定性59不確定性智能體幾乎從來無法了解關(guān)于其環(huán)境的全部事實(shí)。因此其必須在不確定的環(huán)境下行動。概率推理

得到了某一證據(jù)，那么有多大的幾率結(jié)論為真？

例如：我頸部痛;我得腦膜炎的可能有多大?不確定性智能體幾乎從來無法了解關(guān)于其環(huán)境的全部事實(shí)。因此其必60不確定性假如有如下規(guī)則:

iftoothache（牙疼）then原因是cavity（牙齒有洞）但并不是所有牙疼的病人都是因?yàn)檠例X有洞，所以我們可以建立如下規(guī)則:

iftoothacheand?gum-disease（牙齦疾病）and

?filling（補(bǔ)牙）and...thenproblem=cavity以上規(guī)則是復(fù)雜的;更好的方法:

iftoothachethenproblemiscavitywith0.8probability

orP(cavity|toothache)=0.8

theprobabilityofcavityis0.8giventoothacheisobserved不確定性假如有如下規(guī)則:

iftoothache（牙疼）61不確定性 LetactionAt=離起飛時間提前t分鐘動身去機(jī)場

At會使我準(zhǔn)時到達(dá)機(jī)場嗎?

Problems:

1.partialobservability/部分可觀察性(roadstate,otherdrivers‘plans)

2.noisysensors(trafficreports)

3.行動結(jié)果的不確定性(flattire,etc.)

4.immensecomplexityofmodelingandpredictingtraffic

因此一個純粹的邏輯描述方法：

1.risksfalsehood（錯誤風(fēng)險）:“A25

willgetmethereontime”,or

2.leadstoconclusionsthataretooweakfordecisionmaking:

“A25

willgetmethereontimeifthere’snoaccidentonthebridgeanditdoesn‘trainandmytiresremainintactetcetc.”

(A1440

mightreasonablybesaidtogetmethereontimebutI’dhavetostayovernightintheairport…)不確定性 LetactionAt=離起飛時間提前t分62世界與模型中的不確定性Trueuncertainty:rulesareprobabilisticinnature

擲骰子，拋硬幣惰性:把所有意外的規(guī)則都列舉出來是很困難的

花費(fèi)太多時間來確定所有的相關(guān)因素

這些規(guī)則過于繁雜而難以使用理論的無知:某些領(lǐng)域中還沒有完整的理論

(e.g.,medicaldiagnosis)實(shí)踐的無知:掌握了所有規(guī)則但是

并不是所有的相關(guān)信息都能被收集到世界與模型中的不確定性Trueuncertainty:r63處理不確定性的方法概率理論作為一種正式的方法for：

不確定知識的表示和推理

命題中的模型信度(event,conclusion,diagnosis,etc.)

給定可獲得的證據(jù),

A25

willgetmethereontimewithprobability0.04概率是不確定性的語言

現(xiàn)代AI的中心支柱處理不確定性的方法概率理論作為一種正式的方法for：

不確定64Probability概率概率理論提供了一種方法以概括來自我們的惰性和無知的不確定性。Probabilisticassertionssummarizeeffectsof

Laziness（惰性）:failuretoenumerateexceptions（例外）,qualifications（條件）,etc.

Ignorance（理論的無知）:lackofrelevantfacts,initialconditions,etc.Subjectiveprobability（主觀概率）:

Probabilitiesrelatepropositions（命題）toagent'sownstateof

knowledge

e.g.,P(A25|noreportedaccidents)=0.06Thesearenotassertions（斷言）abouttheworld命題的概率隨著新證據(jù)的發(fā)現(xiàn)而改變:

e.g.,P(A25|noreportedaccidents,5a.m.)=0.15Probability概率概率理論提供了一種方法以概括來自我65不確定條件下的決策假設(shè)下述概率是真的:

P(A25getsmethereontime|…)=0.04

P(A90getsmethereontime|…)=0.70

P(A120getsmethereontime|…)=0.95

P(A1440getsmethereontime|…)=0.9999Whichactiontochoose?

Dependsonmypreferences（偏好）formissingflightvs.time

spentwaiting,etc.

Utilitytheory（效用理論）用來對偏好進(jìn)行表示和推理

Decisiontheory=probabilitytheory+utilitytheory

決策理論=概率理論+效用理論不確定條件下的決策假設(shè)下述概率是真的:66Syntax語法基本元素:randomvariable（隨機(jī)變量）

Arandomvariableissomeaspectoftheworldaboutwhichwe(may)haveuncertainty

通常大寫e.g.,Cavity,Weather,Temperature類似于命題邏輯:未知世界被隨機(jī)變量的賦值所定義Booleanrandomvariables（布爾隨機(jī)變量）

e.g.,Cavity（牙洞）(doIhaveacavity?)Discreterandomvariables（離散隨機(jī)變量）

e.g.,Weatherisoneof<sunny,rainy,cloudy,snow>定義域mustbeexhaustive（窮盡的）andmutuallyexclusive（互斥的）Continuousrandomvariables（連續(xù)隨機(jī)變量）

e.g.,Temp=21.6;alsoallow,e.g.,Temp<22.0Syntax語法基本元素:randomvariable（67SyntaxElementaryproposition（命題）constructedbyassignmentofavaluetoarandomvariable:e.g.,Weather=sunny,Cavity=false

(簡寫為?cavity)Complexpropositionsformedfromelementarypropositionsandstandardlogicalconnectivese.g.,Weather=sunny∨Cavity=falseSyntaxElementaryproposition（命68SyntaxAtomicevent:Acompletespecificationofthestateof

theworldaboutwhichtheagentisuncertain原子事件：對智能體無法確定的世界狀態(tài)的一個完

整的詳細(xì)描述。E.g.,iftheworldconsistsofonlytwoBooleanvariablesCavity

andToothache,thenthereare4distinctatomicevents:

Cavity=false∧Toothache=false

Cavity=false∧Toothache=true

Cavity=true∧Toothache=false

Cavity=true∧Toothache=true

Atomiceventsaremutuallyexclusiveandexhaustive

窮盡和互斥SyntaxAtomicevent:Acomplete69概率公理對任意命題A,B

0≤P(A)≤1

P(true)=1andP(false)=0

P(A∨B)=P(A)+P(B)-P(A∧B)

概率公理對任意命題A,B

0≤P(A)≤1

P70Priorprobability（先驗(yàn)概率）Priororunconditionalprobabilities（無條件概率）ofpropositions在沒有任何其它信息存在的情況下關(guān)于命題的信度

e.g.,P(Cavity=true)=0.1andP(Weather=sunny)=0.72correspondtobeliefpriortoarrivalofany(new)evidenceProbabilitydistributiongivesvaluesforallpossibleassignments:概率分布給出一個隨機(jī)變量所有可能取值的概率

P(Weather)=<0.72,0.1,0.08,0.1>(normalized（歸一化的）,i.e.,sumsto1)Jointprobabilitydistributionforasetofrandomvariablesgivestheprobabilityofeveryatomiceventonthoserandomvariables(i.e.,everysamplepoint)聯(lián)合概率分布給出一個隨機(jī)變量集的值的全部組合的概率

P(Weather,Cavity)=a4×2matrixofvalues:EveryquestionaboutadomaincanbeansweredbythejointdistributionbecauseeveryeventisasumofsamplepointsPriorprobability（先驗(yàn)概率）Prioro71連續(xù)變量的概率Expressdistributionasaparameterized（參數(shù)化的）functionofvalue:P(X=x)=U[18,26](x)=uniform（均勻分布）densitybetween18and26連續(xù)變量的概率Expressdistributionas72連續(xù)變量的概率連續(xù)變量的概率73MarginalDistributions（邊緣概率分布）Marginaldistributionsaresub-tableswhicheliminatevariablesMarginalization(summingout):CombinecollapsedrowsbyaddingMarginalDistributions（邊緣概率分布）74Conditionalprobability（條件概率）Conditionalorposteriorprobabilities（后驗(yàn)概率）P(a|b)

證據(jù)累積過程的形式化和發(fā)現(xiàn)新證據(jù)后的概率更新

當(dāng)一個命題為真的條件下，指定命題的概率

e.g.,P(cavity|toothache)=0.8

i.e.,鑒于牙疼是已知證據(jù)

(Notationforconditionaldistributions（條件概率分布）:

P(cavity|toothache)=asinglenumber

P(Cavity,Toothache)=2x2tablesummingto1

P(Cavity|Toothache)=2-elementvectorof2-elementvectorsIfweknowmore,e.g.,cavityisalsogiven,thenwehave

P(cavity|toothache,cavity)=1

新證據(jù)可能是不相關(guān)的，可以簡化,e.g.,

P(cavity|toothache,sunny)=P(cavity|toothache)=0.8Conditionalprobability（條件概率）C75條件概率定義條件概率為:

P(a|b)=P(a∧b)/P(b)ifP(b)>0Productrule（乘法規(guī)則）

givesanalternativeformulation:

P(a∧b)=P(a|b)P(b)=P(b|a)P(a)Ageneralversionholdsforwholedistributions,e.g.,

P(Weather,Cavity)=P(Weather|Cavity)P(Cavity)(Viewasasetof4×2equations,notmatrixmultiplication)Chainrule（鏈?zhǔn)椒▌t）isderivedbysuccessiveapplicationofproductrule:條件概率定義條件概率為:

P(a|b)=P(a∧76條件概率條件概率跟標(biāo)準(zhǔn)概率一樣,forexample:

0<=P(a|e)<=1

conditionalprobabilitiesarebetween0and1inclusive

P(a1|e)+P(a2|e)+...+P(ak|e)=1

conditionalprobabilitiessumto1wherea1,…,ak

areallvaluesinthedomainofrandomvariableA

P(?a|e)=1-P(a|e)

negationforconditionalprobabilities條件概率條件概率跟標(biāo)準(zhǔn)概率一樣,forexample:

77通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:Foranypropositionφ,sumtheatomiceventswhereitistrue:一個命題的概率等于所有當(dāng)它為真時的原子事件的概率和

通過枚舉的推理Startwiththejointpr78通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:Foranypropositionφ,sumtheatomiceventswhereitistrue:一個命題的概率等于所有當(dāng)它為真時的原子事件的概率和

通過枚舉的推理Startwiththejointpr79通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:Foranypropositionφ,sumtheatomiceventswhereitistrue:一個命題的概率等于所有當(dāng)它為真時的原子事件的概率和

通過枚舉的推理Startwiththejointpr80通過枚舉的推理Startwiththejointprobabilitydistribution（全聯(lián)合概率分布）:通過枚舉的推理Startwiththejointpr81Normalization（歸一化）Denominator（分母）canbeviewedasanormalizationconstantα

P(Cavity|toothache)=αP(Cavity,toothache)

=α[P(Cavity,toothache,catch)+P(Cavity,toothache,?catch)]

=α[<0.108,0.016>+<0.012,0.064>]

=α<0.12,0.08>=<0.6,0.4>

Generalidea:computedistributiononqueryvariablebyfixing

evidencevariables（證據(jù)變量）andsummingoverhidden

variables（未觀測變量）Normalization（歸一化）Denominator（82通過枚舉的推理Typically,weareinterestedin

theposteriorjointdistributionofthequeryvariables（查詢變量）Y

givenspecificvaluesefortheevidencevariables（證據(jù)變量）ELetthehiddenvariables（未觀測變量）beH=X-Y–EThentherequiredsummationofjointentriesisdonebysummingoutthehiddenvariables:

P(Y|E=e)=αP(Y,E=e)=αΣhP(Y,E=e,H=h)ThetermsinthesummationarejointentriesbecauseY,EandHtogetherexhaustthesetofrandomvariables（Y,E,H構(gòu)成了域中所有變量的完整集合）Obviousproblems:

1.Worst-casetimecomplexityO(dn)wheredisthelargestarity

2.SpacecomplexityO(dn)tostorethejointdistribution

3.HowtofindthenumbersforO(dn)entries?通過枚舉的推理Typically,weareinter83Independence（獨(dú)立性）AandBareindependentiff

P(A|B)=P(A)orP(B|A)=P(B)orP(A,B)=P(A)P(B)E.g:rollof2die:P({1},{3})=1/6*1/6=1/36P(Toothache,Catch,Cavity,Weather)=P(Toothache,Catch,Cavity)P(Weather)32entriesreducedto12;fornindependentbiasedcoins,O(2n)→O(n)Absoluteindependencepowerfulbutrare絕對獨(dú)立強(qiáng)大但罕見Dentistry（牙科領(lǐng)域）isalargefieldwithhundredsofvariables,noneofwhichareindependent.Whattodo?Independence（獨(dú)立性）AandBarei84獨(dú)立的濫用天真的數(shù)學(xué)笑話：一個著名統(tǒng)計學(xué)家永遠(yuǎn)不會坐飛機(jī)旅行,因?yàn)樗芯苛撕娇章眯泻凸烙?任何給定的航班上有炸彈的可能性是一百萬分之一,他不準(zhǔn)備接受這些可能性。有一天，一位同時在遠(yuǎn)離家鄉(xiāng)的會議上遇到他?！澳阍趺吹竭@里的？坐火車嗎？”“不，我飛過來的”“Whataboutthepossibilityofabomb?”“Well,Ibeganthinkingthatiftheoddsofonebombare1:million,thentheoddsoftwobombsare(1/1,000,000)x(1/1,000,000).Thisisavery,verysmallprobability,whichIcan