From Statistical Knowledge Bases to Degrees of BeliefAn Overview

∗

AnOverview

ComputerScienceDept.

CornellUniversity

http://www.cs.cornell.edu/home/halpern

JosephY.Halpern

†

halpern@cs.cornell.edu

ABSTRACT

Anintelligentagentwilloftenbeuncertainaboutvariouspropertiesofitsenvironment,andwhenactinginthatenvi-ronmentitwillfrequentlyneedtoquantifyitsuncertainty.Forexample,iftheagentwishestoemploytheexpected-utilityparadigmofdecisiontheorytoguideitsactions,shewillneedtoassigndegreesofbelief(subjectiveprobabili-ties)tovariousassertions.Ofcourse,thesedegreesofbeliefshouldnotbearbitrary,butrathershouldbebasedontheinformationavailabletotheagent.Thispaperprovidesabriefoverviewofoneapproachforinducingdegreesofbe-lieffromveryrichknowledgebasesthatcanincludeinfor-mationaboutparticularindividuals,statisticalcorrelations,physicallaws,anddefaultrules.Theapproachiscalledtherandom-worldsmethod.Themethodisbasedontheprinci-pleofindifference:ittreatsalloftheworldstheagentcon-siderspossibleasbeingequallylikely.Itisabletointegratequalitativedefaultreasoningwithquantitativeprobabilisticreasoningbyprovidingalanguageinwhichbothtypesofin-formationcanbeeasilyexpressed.Anumberofdesideratathatariseindirectinference(reasoningfromstatisticalin-formationtoconclusionsaboutindividuals)anddefaultrea-soningfollowdirectlyfromthesemanticsofrandomworlds.Forexample,randomworldscapturesimportantpatternsofreasoningsuchasspecificity,inheritance,indifferencetoirrelevantinformation,anddefaultassumptionsofindepen-dence.Furthermore,theexpressivepowerofthelanguageusedandtheintuitivesemanticsofrandomworldsallowthe

manner;wecallthismethodtherandom-worldsmethod.Mytalkwillfocusonthisworkbecause,althoughitisnotsorecent,itdoesseemquiterelevanttorecentworkinthedatabasecommunity.HereIbrieflyreviewtheapproach(almostallthediscussionistakenfrom[4],withverylittlechange)anddiscusstheconnectiontodatabasework.

Therehasbeenagreatdealofworkaddressingaspectsofthisgeneralproblem.Twolargebodiesofworkthatareparticularlyrelevantaretheworkondirectinference,go-ingbacktoReichenbach[25],andthevariousapproachestononmonotonicreasoning.Directinferencedealswiththeproblemofderivingdegreesofbelieffromstatisticalinfor-mation,typicallybyattemptingtofindasuitablereferenceclasswhosestatisticscanbeusedtodeterminethedegreeofbelief.Forinstance,asuitablereferenceclassforthepa-tientEricmightbetheclassofallpatientswithjaundice.Whiledirectinferenceisconcernedwithstatisticalknowl-edge,nonmonotonicreasoningdealsmostlywithknowledgebasesthatcontaindefaultrules.Noneofthesystemspro-posedforeitherreference-classreasoningornonmonotonicreasoningcandealadequatelywiththelargeandcomplexknowledgebasesthatweareinterestedin.Inparticular,nonecanhandlerichknowledgebasesthatmaycontainacombinationoffirst-order,default,andstatisticalinforma-tion.

WeassumethattheinformationintheknowledgebaseisexpressedinavariantofthelanguageintroducedbyBac-chus[1].Bacchus’slanguageaugmentsfirst-orderlogicbyallowingstatementsoftheform󰀈Hep(x)|Jaun(x)󰀈x=0.8,whichsaysthat80%ofpatientswithjaundicehavehepati-tis.Notice,however,thatinfinitemodelsthisstatementhasthe(probablyunintended)consequencethatthenumberofpatientswithjaundiceisamultipleof5.Toavoidthisprob-lem,weuseapproximateequalityratherthanequality,writ-ing󰀈Hep(x)|Jaun(x)󰀈x≈0.8,read“approximately80%ofpatientswithjaundicehavehepatitis”.Intuitively,thissaysthattheproportionofjaundicedpatientswithhepatitisiscloseto80%:i.e.,withinsometoleranceτof0.8.Thisinter-pretationseemsquiteappropriatefordatabaseapplications,whereitisunlikelythatwewillbecompletelyconfidentinthestatisticsthatwehave.Theuseofapproximateequal-ityhasthefurtheradvantageoflettingusexpressdefaultinformation.Weinterpretastatementas“Birdstypicallyfly”asexpressingthestatisticalassertion“Almostallbirdsfly”.Usingapproximateequality,wecanrepresentthisas󰀈Fly(x)|Bird(x)󰀈x≈1.(Thisinterpretationiscloselyre-latedtovariousapproachesapplyingprobabilisticsemanticstononmonotoniclogic;seePearl[24]foranoverview.)

Havingdescribedthelanguageinwhichourknowledgebaseisexpressed,wenowneedtodecidehowtoassignde-greesofbeliefgivenaknowledgebase.Perhapsthemostwidelyusedframeworkforassigningdegreesofbelief(whichareessentiallysubjectiveprobabilities)istheBayesianparadigm.There,oneassumesaspaceofpossibilitiesandaprobabil-itydistributionoverthisspace(thepriordistribution),andcalculatesposteriorprobabilitiesbyconditioningonwhatisknown(inourcase,theknowledgebase).Tousethisap-proach,wemustspecifythespaceofpossibilitiesandthedistributionoverit.InBayesianreasoning,thereisrela-tivelylittleconsensusastohowthisshouldbedoneingen-eral.Indeed,theusualphilosophyisthatthesedecisionsaresubjective.

Ourapproachisdifferent.WeassumethattheKBcon-tainsalltheknowledgetheagenthas,andweallowaveryexpressivelanguagesoastomakethisassumptionreason-able.ThisassumptionmeansthatanyknowledgetheagenthasthatcouldinfluencethepriordistributionisalreadyincludedintheKB.Asaconsequence,wegiveasingleuniformconstructionofaspaceofpossibilitiesandadis-tributionoverit.Oncewehavethisprobabilityspace,wecanusetheBayesianapproach:TocomputetheprobabilityofanassertionφgivenKB,weconditiononKB,andthencomputetheprobabilityofφusingtheresultingposteriordistribution.

Sohowdowechoosetheprobabilityspace?Onegeneralstrategy,discussedbyHalpern[18],istogivesemanticstodegreesofbeliefintermsofaprobabilitydistributionoverasetofpossibleworlds,orfirst-ordermodels.Thissemanticsclarifiesthedistinctionbetweenstatisticalassertionsandde-greesofbelief.Assuggestedabove,astatisticalassertionsuchas󰀈Hep(x)|Jaun(x)󰀈x≈0.8istrueorfalseinapartic-ularworld,dependingonhowmanyjaundicedpatientshavehepatitisinthatworld.Ontheotherhand,adegreeofbeliefisneithertruenorfalseinaparticularworld—ithasseman-ticsonlywithrespecttotheentiresetofpossibleworldsandaprobabilitydistributionoverthem.Thereisnonecessaryconnectionbetweentheinformationintheagent’sKBandthedistributionoverworldsthatdeterminesherdegreesofbelief.However,weclearlywanttheretobesomeconnec-tion.Inparticular,wewanttheagenttobaseherdegreesofbeliefsonherinformationabouttheworld,includingherstatisticalinformation.Therandom-worldsmethodturnsouttobeapowerfultechniqueforaccomplishingthis.

Todefineourprobabilityspace,wehavetochooseanappropriatesetofpossibleworlds.Givensomedomainofindividuals,westipulatethatthesetofworldsissimplythesetofallfirst-ordermodelsoverthisdomain.Thatis,apos-sibleworldcorrespondstoaparticularwayofinterpretingthesymbolsintheagent’svocabularyoverthedomain.Inourcontext,wecanassumethatthe“trueworld”hasafinitedomain,sayofsizeN.Infact,withoutlossofgenerality,weassumethatthedomainis{1,...,N}.

Havingdefinedtheprobabilityspace(thesetofpossibleworlds),wemustconstructaprobabilitydistributionoverthisset.Forthis,wegiveperhapsthesimplestpossibledef-inition:weassumethatallthepossibleworldsareequallylikely(thatis,eachworldhasthesameprobability).Thiscanbeviewedasanapplicationoftheprincipleofindif-ference.Sinceweareassumingthatalltheagentknowsisincorporatedinherknowledgebase,theagenthasnoapri-orireasontopreferoneworldovertheother.Itisthereforereasonabletoviewallworldsasequallylikely.Interestingly,theprincipleofindifference(sometimesalsocalledtheprin-cipleofinsufficientreason)wasoriginallypromotedaspartoftheverydefinitionofprobabilitywhenthefieldwasorigi-nallyformalizedbyJacobBernoulliandothers;theprinciplewaslaterpopularizedfurtherandappliedwithconsiderablesuccessbyLaplace.(See[17]forahistoricaldiscussion.)Itlaterfellintodisreputeasageneraldefinitionofprobabil-ity,largelybecauseoftheexistenceofparadoxesthatarisewhentheprincipleisappliedtoinfiniteorcontinuousprob-abilityspaces.However,theprincipleofindifferencecanbeanaturalandeffectivewayofassigningdegreesofbeliefincertaincontexts,andinparticular,inthecontextwherewerestrictattentiontoafinitecollectionofworlds.

Inanycase,combiningthechoiceofpossibleworldswith

theprincipleofindifference,weobtainapriordistribution.WecannowinduceadegreeofbeliefinφgivenKBbyconditioningonKBtoobtainaposteriordistributionandthencomputingtheprobabilityofφaccordingtothisnewdistribution.Itiseasytoseethat,sinceeachworldisequallylikely,thedegreeofbeliefinφgivenKBisthefractionofpossibleworldssatisfyingKBthatalsosatisfyφ.

Oneproblemwiththeapproachasstatedsofaristhat,ingeneral,wedonotknowthedomainsizeN.Typically,how-ever,Nisknowntobelarge.WethereforeapproximatethedegreeofbeliefforthetruebutunknownNbycomputingthelimitingvalueofthisdegreeofbeliefasNgrowslarge.Theresultistherandom-worldsmethod.(Ofcourse,ifadatabaseincludesinformationaboutthedomainsize,thenwecanjustuseit.)

Thekeyideasintheapproacharenotnew.ManyofthemcanbefoundintheworkofJohnson[19]andCar-nap[6,7],althoughtheseauthorsfocusonknowledgebasesthatcontainonlyfirst-orderinformation,andforthemostpartrestricttheirattentiontounarypredicates.RelatedapproacheshavebeenusedinthemorerecentworksofShas-tri[28]andofParisandVencovska[23],inthecontextofaunarystatisticallanguage.Chuaqui[10]sharestheideaofbasingatheoryofprobabilisticreasoninguponnotionsofindifferenceandsymmetry,althoughthedetailsofhisapproacharequitedifferentfromours.

Havingdefinedthemethod,howdowejudgeitsreason-ableness?Fortunately,aswementioned,therearetwolargebodiesofworkonrelatedproblemsfromwhichwecandrawguidance:reference-classreasoninganddefaultreasoning.Whilenoneofthesolutionssuggestedfortheseproblemsseemsentirelyadequate,theyearsofresearchhaveresultedinsomestrongintuitionsregardingwhatanswersareintu-itivelyreasonableforcertaintypesofqueries.Interestingly,theseintuitionsoftenleadtoidenticaldesiderata.Inpar-ticular,mostsystems(ofbothtypes)espousesomeformofpreferenceformorespecificinformationandtheabilitytoignoreirrelevantinformation.Weshowthattherandom-worldsapproachsatisfiesthesedesiderata.Moreover,intheabsenceofinformation,therandom-worldmethodmakesattributesindependent.Ratherthanhavingtoassumein-dependence,asisdoneinmanyapplications,itisaprov-ableconsequenceoftheapproach.Infact,alltheseprop-ertiesfollowfromtwogeneraltheorems.Weprovethat,inthosecaseswherethereisaspecificpieceofstatisticalin-formationthatshould“obviously”beusedtodetermineadegreeofbelief,randomworldsdoesinfactusethisinfor-mation.Thedifferentdesiderata,suchasapreferenceformorespecificinformationandanindifferencetoirrelevantinformationfollowaseasycorollaries.Wealsoshowthatrandomworldsprovidesreasonableanswersinmanyothercontexts,notcoveredbythestandardspecificityandirrele-vanceheuristics.Thus,therandom-worldsmethodisindeedapowerfulone,thatcandealwithrichknowledgebasesandstillproducetheanswersthatpeoplehaveidentifiedasbeingthemostappropriateones.

Ofcourse,totheextentthatwearegoingtousethemethod,wehavetocalculatedegreesofbelief.Ingeneral,theproblemofdecidingwhetherthedegreeofbeliefevenexists(thatis,whetherthereisalimitingprobability)isundecidable[16,20].Wecangetdecidabilityifwerestricttounaryknowledgebases,wheretherearenofunctionsym-bolsandallpredicatesareunary[15,20].Moreimportantly,

asshownin[14],thereisacloseconnectionbetweenrandomworldsandmaximumentropyinthecaseofunaryknowledgebases.Basedonthisconnection,weshowthatinmanycasesofinterestamaximum-entropycomputationcanbeusedtocalculateanagent’sdegreeofbelief.

Theconnectionbetweenrandomworldsonmaximumen-tropyreliescriticallyontheassumptionthatwearecon-ditioningonaunaryformula.Infact,inalmostallappli-cationswheremaximumentropyhasbeenused(andwhereitsapplicationcanbebestjustifiedintermsoftherandom-worldsmethod)theknowledgebaseisdescribedintermsofunarypredicates(or,equivalently,unaryfunctionswithafiniterange).Forexample,inphysicsapplicationsweareinterestedinsuchpredicatesasquantumstate(see[13]).AIapplicationsandexpertsystemsalsooftenuseonlyunarypredicates[9]suchassymptomsanddiseases.Ingeneral,manypropertiesofinterestcanbeexpressedusingunarypredicates,sincetheyexpresspropertiesofindividuals.In-deed,agoodcasecanbemadethatstatisticianstendtoreformulateallproblemsintermsofunarypredicates,sinceaneventinasamplespacecanbeidentifiedwithaunarypredicate[27].Infact,inmostcaseswherestatisticsareused,wehaveabasicunitinmind(anindividual,afamily,ahousehold,etc.),andtheproperties(predicates)wecon-sideraretypicallyrelativetoasingleunit(i.e.,unarypred-icates).Thus,resultsconcerningcomputingtheasymptoticconditionalprobabilityifweconditiononunaryformulasaresignificantinpractice.

Ontheotherhand,fordatabaseapplications,itisquitestandardtoseebinaryrelationlike“Manager-of”.Notethattherandom-worldsmethodmakessenseforpredicatesofarbitraryarity;itisjusttheconnectiontomaximumentropythatislost.

Moregenerally,howdoestherandom-worldsmethodre-latetoworkindatabases?Ibrieflydiscussafewpointsofcontact:

•Oneapplicationisobvious:Therearemanystatis-ticaldatabasesavailable,suchasthosederivedfromcensusdataandeconomicdata.Therandom-worldsmethodgivesaprincipledmethodofderivingconclu-sionsaboutparticularindividualsbasedonthestatis-ticalinformation.•Therehasalsobeenagreatdealofwork,especiallyre-cently,onprobabilisticandimprecisedatabases;see,forexample,[8]andthemorerecent[5]and[12]andthereferencestherein.1Probabilisticdatabasesallowprobabilitiestobeassociatedwithtuples.Roughlyspeaking,theprobabilityrepresentsthelikelihoodthatthetupleisinthedatabase.Insomesettings,theprob-abilityisbestinterpretedasstatisticalinformation.Forexample,Burdicketal.[5]giveanexampleofanautomobiledatabasethatlistsmakesofcarsandtheproblemfromwhichtheyaresuffering(“brakeprob-lem”,“transmissionproblem”,etc.).Theprobabilisticinformationcouldbeinterpretedassummarizingsta-tisticalinformation,inwhichcasethetechniquesusedhereapplyimmediatelytodrawconclusions.Alterna-tively,itcouldbeinterpretedasrepresentingadegree

ofbelief(anagent’ssubjectivebeliefthat,say,thecarissufferingfromabrakeproblem).Themethodasde-scribedcannotdealwithknowledgebasesthatincludedegreesofbelief;however,in[3],wediscussthreewaysthattherandom-worldsmethodcanbeextendedtohandledegreesofbelief.

•Random-worldsstylemethodshavebeenusedtodefinenotionsofprivacy,whereallinstancesofadatabaseconsistentwithwhatisknownareconsideredequallylikely;cf.[22].Itseemsthatthereisnowagreatdealofinterestinthedatabasecommunityinfindingwaystodrawinferencesfromdatabasesthatincludeincompleteandimprecisein-formation.Therandom-worldsmethodandotherrelatedapproaches(see[2])mayprovetobeausefultoolfordo-ingthis.Indeed,asIhavementioned,random-worldsstylemethodshavealreadybeenusedinthecontextofprivacy;theyhavealsobeenusedinanalyzingprobabilisticdatabases[11].Isuspectthatmoreapplicationswillbefoundaswell.

2.REFERENCES

[1]F.Bacchus.RepresentingandReasoningwith

ProbabilisticKnowledge.MITPress,Cambridge,Mass.,1990.

[2]F.Bacchus,A.J.Grove,J.Y.Halpern,andD.Koller.

Fromstatisticstobelief.InProc.TenthNationalConferenceonArtificialIntelligence(AAAI’92),pages602–608.1992.

[3]F.Bacchus,A.J.Grove,J.Y.Halpern,andD.Koller.

Generatingnewbeliefsfromold.InProc.TenthConferenceonUncertaintyinArtificialIntelligence(UAI’94),pages37–45,1994.

[4]F.Bacchus,A.J.Grove,J.Y.Halpern,andD.Koller.

Fromstatisticalknowledgebasestodegreesofbelief.ArtificialIntelligence,87(1–2):75–143,1996.[5]D.Burdick,P.M.Deshpande,T.S.Jayram,

R.Ramakrishnan,andS.Vaithyanathan.OLAPoveruncertainandimprecisedata.InVLDB’05,

Proceedingsofthe31stInt.ConferenceonVeryLargeDatabases,pages970–981,2005.

[6]R.Carnap.LogicalFoundationsofProbability.

UniversityofChicagoPress,Chicago,1950.

[7]R.Carnap.TheContinuumofInductiveMethods.

UniversityofChicagoPress,Chicago,1952.[8]R.CavalloandM.Pittarelli.Thetheoryof

probabilisticdatabases.InVLDB’87,Proceedingsofthe13thInt.ConferenceonVeryLargeDatabases,pages71–87,1987.

[9]P.C.Cheeseman.Amethodofcomputinggeneralized

Bayesianprobabilityvaluesforexpertsystems.InProc.EighthInternationalJointConferenceonArtificialIntelligence(IJCAI’83),pages198–202.1983.

[10]R.Chuaqui.Truth,Possibility,andProbability:New

LogicalFoundationsofProbabilityandStatisticalInference.North-Holland,Amsterdam,1991.

[11]N.DalviandD.Suciu.Efficientqueryevaluationon

probabilisticdatabases.InVLDB’04,Proceedingsofthe30thInt.ConferenceonVeryLargeDatabases,pages8–875,2004.

[12]N.Dalvi,G.Miklau,andD.Suciu.Asymptotic

conditionalprobabilitiesforconjunctivequeries.InProc.InternationalConferenceonDatabaseTheory,pages287–303,2005.

[13]K.G.DenbighandJ.S.Denbigh.EntropyinRelation

toIncompleteKnowledge.CambridgeUniversityPress,Cambridge,U.K.,1985.

[14]A.J.Grove,J.Y.Halpern,andD.Koller.Random

worldsandmaximumentropy.JournalofA.I.Research,2:33–88,1994.

[15]A.J.Grove,J.Y.Halpern,andD.Koller.Asymptotic

conditionalprobabilities:thenon-unarycase.JournalofSymbolicLogic,61(1):250–275,1996.

[16]A.J.Grove,J.Y.Halpern,andD.Koller.Asymptotic

conditionalprobabilities:theunarycase.SIAMJournalonComputing,25(1):1–51,1996.

[17]I.Hacking.TheEmergenceofProbability.Cambridge

UniversityPress,Cambridge,U.K.,1975.

[18]J.Y.Halpern.Ananalysisoffirst-orderlogicsof

probability.ArtificialIntelligence,46:311–350,1990.[19]W.E.Johnson.Probability:Thedeductiveand

inductiveproblems.Mind,41(1):409–423,1932.[20]M.I.Liogon’ki˘ı.Ontheconditionalsatisfiabilityratio

oflogicalformulas.MathematicalNotesoftheAcademyoftheUSSR,6:856–861,1969.

[21]R.D.LuceandH.Raiffa.GamesandDecisions.

Wiley,NewYork,1957.

[22]A.Machanavajjhala,J.Gehrke,D.Kifer,andM.

Venkitasubramanian,ℓ-diversity:privacybeyondk-anonymity.InProc.Int.Conf.DataEngineering(ICDE2006),2006.

[23]J.B.ParisandA.Vencovska.Ontheapplicabilityof

maximumentropytoinexactreasoning.InternationalJournalofApproximateReasoning,3:1–34,19.[24]J.Pearl.Probabilisticsemanticsfornonmonotonic

reasoning:asurvey.InProc.FirstInternational

ConferenceonPrinciplesofKnowledgeRepresentationandReasoning(KR’),pages505–516,19.

ReprintedinG.ShaferandJ.Pearl(Eds.),ReadingsinUncertainReasoning,pp.699–710.SanFrancisco:MorganKaufmann,1990.

[25]H.Reichenbach.TheTheoryofProbability.University

ofCaliforniaPress,Berkeley,1949.TranslationandrevisionofGermanedition,publishedasWahrscheinlichkeitslehre,1935.

[26]L.J.Savage.FoundationsofStatistics.Wiley,New

York,1954.

[27]G.Shafer.Personalcommunication,1993.

[28]L.Shastri.Defaultreasoninginsemanticnetworks:a

formalizationofrecognitionandinheritance.ArtificialIntelligence,39(3):285–355,19.