Cellular-Automata-Generalized-to-an-Inferential-System：元胞自動機廣義推理系統(tǒng)-課件

CellularAutomataGeneralizedToAnInferentialSystemDavidJ.BlowerCogonSystemsPensacolaFL27thInternationalWorkshoponBayesianInferenceandMaximumEntropyMethodsinScienceandEngineering,SaratogaSprings,NewYork,11July2019MotivationWhyisitimpossibletopredictthebehaviourofacellularautomaton?TheMotivatingQuestionButisn’tthequintessentialfeatureofprobabilitytheoryandinferentialsystemstheabilitytopredictfutureevents?ProposedSolutionJaynesusedprobabilitytheorytogeneralizeclassicallogicfunctions.TreatCAfromaninferentialandinformationalpointofview.WhyExamineCellularAutomata?BecauseCellularAutomataareastand-inforanysufficientlydetailedcomplicatedontologicalexplanationforhowtheworldworks.IssuesinOrderAddressedBooleanAlgebraLogicFunctionsCellularAutomataWhyStartwithBooleanAlgebra?ThefollowingfewslidesonBooleanAlgebraaresolelytosetthestageforanalogousoperationswithclassicallogicfunctions(andcellularautomata).SomeBasicBooleanQuestionsHowareBooleanfunctionsdefined?HowaresyntacticallycorrectBooleanformulasproduced?WhatisagoodcanonicalexpressionforBooleanfunctions?WhyIsItHelpful?UsefulforbothlogicfunctionsandcellularautomataAxiomsofBooleanAlgebrausedinBayes’sTheoremCanonicalexpressionssubstitutedforcomplicatedlogicandCArulesFormalRules,BooleanAlgebra,andProbabilityTheoryPerfectchoicefordiscussingformalmanipulationrulesofprobabilitytheorywheretheactualnumericalassignmentsarenottheissue.BooleanAlgebraonafinitecarriersetisa“closed”system,thatis,thereisalwaysananswer.Moreover,neithernumbersnorarithmeticoperationsarerequiredtofindthatanswer.BooleanAlgebraThecarriersetBinaryoperatorsSpecialElementsFunctiondefinition:Amappingfromthesetoforderedpairsofthecarriertoanelementinthecarrierset.CharacterizedbythequintupleBooleanAlgebraAnexampleofacarriersetwithfourelementsAll16orderedpairsfromthecarriersetAmappingfromanelementofBxBintoanelementofBExampleofBooleanFunctionFunctionTableBooleanFormulaSubstitutespecificargumentsBoole’sExpansionTheoremAnyBooleanfunctioncanbeexpandedinthefollowingmanner.Applyingthistheoreminarecursivemanneryieldsthedisjunctivenormalform(DNF).DisjunctiveNormalFormForexample,hereistheexpansionofanyBooleanfunction

f(x,y)

with

n=2

arguments.Thesearecalledthediscriminants.DisjunctiveNormalFormCalculatediscriminantsandthensubstituteRepeatinggenericexpansionfrompreviousslideIssuesinOrderAddressedBooleanAlgebraLogicFunctionsCellularAutomataLogicFunctionsAspecialcaseofBooleanAlgebraDifferentNotationFunctionswithtwoargumentswritteningenericBooleanAlgebranotationandtheninClassicalLogicnotation.Boole’sExpansionTheoremUsingBoole’sexpansiontheorem,theDNFforanylogicfunctionnowlookslike,TheDNFforLogicFunctionsSincethediscriminantsalwaystakeafunctionalassignmentofeitherTRUEorFALSE,atypicalexpansionmightlooksomethinglikethis,ThelogicfunctionthatreturnsBwhenargumentsAandBgiven.f10(A,B)onnextslide.All16LogicFunctionsClassicalSyllogismModusPonensAisTRUEAimpliesBTherefore,BisTRUEClassicalSyllogismRecapitulateJaynes’sdemonstrationgeneralizingclassicallogicwithprobabilitytheory(buthereIemphasizetheBooleanAlgebraaspects).

**Chapter2,pp.35--36GeneralizingClassicalLogicBayes’sTheoremSubstituteDNFexpansionofImplicationfunctionABBooleanoperationsreduceabovetoModusPonensSubstitutetheshortenedDNFexpansionfortheimplicationfunctioninBayes’sTheoremBayes’sTheoremnowlookslikethisModusPonensBooleanoperationsondenominatorBooleanoperationsonnumeratorBayes’sTheoremDifferentApproachNowsolvemodusponensusingajointprobabilitytable.

Theanswershouldbethesame.JointProbabilityTableTwostatementsAandBeachtakeononlytwovalues.Therearefourcellsinthejointprobabilitytable.ThemodelassigningthesenumericalvaluesistheimplicationfunctionAB.JointProbabilityTableThesameanswerasbefore.ThemodelMkassignslegitimatenumericalvaluestothejointstatementsinthefourcellsofthejpt.Themodelistheimplicationfunction.Cell1Cell1Cell3ProbabilityTheoryGeneralizesClassicalLogicAssumethesamelogicfunction,butnowBisTRUE.

WhatistheimpactonA?Hereisan“invalid’’logicalargument,butonethatiseasilysolvedusingprobabilitytheoryinexactlythesamemannerasbefore.The“Invalid”LogicalArgumentSolvedbyProbabilityTheoryUsethenumericalassignmentsfromthejointprobabilitytable.Probabilitytheoryasageneralizationoflogicreturnsananswer,whileclassicallogicrefusestoaddresstheissuecallingit“undecidable.”Placementof0sinJPTCell3indexesjointstatement:AisTRUEandBisFALSE.f13(A,B)hasfunctionalassignmentofFALSEifAisTRUEandBisFALSEbyverydefinitionofoperator.

Therefore,cell3MUSTHAVEanumericalassignmentof0underthismodel.IssuesinOrderAddressedBooleanAlgebraLogicFunctionsCellularAutomataElementaryOne-DimensionalCellularAutomataWolfram’sfamousexampleofaCAproventobeaUniversalTuringMachineElementaryOne-DimensionalCellularAutomataFirstfewstepsofaCAfollowingRule110ManyStepsofCAFollowingRule110InteractingLocalizedStructures.Theycomputeanythingthatcanbecomputed!!Ourstand-inforacomplicateddetailedontologicalmodeloftheworld.LogicFunctionswithThreeVariablesButRule110issimplyalogicfunctionwiththreeargumentsinsteadofthetwoargumentsaswehaveexaminedpreviouslyindiscussingclassicallogic.Thereareatotalof256possiblelogicfunctionswiththreevariablesandRule110isoneofthose256functions.HereisRule110’sfunctiontableforalleightpossiblesettingsofthethreevariables.BlackTWhiteFTheDNFforRule110And,likeanylogicfunction,Rule110canbeexpandedviatheDNF.TheDNFexpansionofathreevariablelogicfunction,Rule110.TheDNFand0sintheJPTAnd,justaswedidwhenexaminingmodusponens,wecanusetheDNFexpansionofalogicfunctiontolocatethe0sinajointprobabilitytable.WewillemploythejptasaneasieralternativetotheformalBooleanoperationsinsolvingBayes’sTheoremappliedtoCA.JointProbabilityTablewithNumericalAssignmentsFollowingRule110Placementof0sdictatedbymodelfollowinglogicfunctionf110(A,B,C)JointProbabilityTablewithNumericalAssignmentsFollowingRule110BN+1cannotbeTRUE

(black)ifAN,BNandCNarealsoTRUE

(black)JointProbabilityTablewithNumericalAssignmentsFollowingRule110TheDNFexpansionofRule110alsotellsuswherethenon-0smustbeplaced.IffunctionalassignmentBN+1isTRUEatthesefiveterms,non-zeroprobabilityisassigned.Or,0sareplacedwherefunctionalassignmentis

FALSE.Bayes’sTheoremforRule110Writeoutthegenerictemplateforupdatingastateofknowledge(Bayes’sTheorem,ofcourse)aboutthecelltobeupdatedgiventhecolorsofthreecellsattheprevioustimestepandthenumericalassignmentfollowingRule110.UpdatingColorofCellinCAUsingBayes’sTheoremLocateandinsertvaluesfromjpt.InsertthenumericalassignmentfromCell12inthenumeratorandthenumericalassignmentfromCells12and4inthedenominator.Bayes’sTheoremwithdenominatorexpanded.NumericalassignmentfollowsfrommodelimplementingRule110.WhatisthePoint?Jaynesgeneralizedlogicfunctions(Booleanfunctions)bytreatingthemfromaprobabilisticandinferentialstandpoint.CAarecomposedofBooleanfunctions,sothinkofthemnotfromthedeductiveviewpoint,butratherfromaninformationalstandpoint.Forexample,letawiderangeofmodelsinsertlegitimatenumericalvaluesintothecellsofajointprobabilitytableforaCA.SupposethereisalackofinformationaboutwhichmodelcorrectlygovernstheevolutionoftheCA.Then,asaconsequenceensuingforallinformationalsystems,predictionatleastbecomesafeasibleconcepttoexplore.DifferentModelsAssignDifferentNumericalValues“Almost”themodel.

HowDoWePredictFutureEventsinanInferentialSystem?Weusethesameformalmanipulationruleswealwaysuseinprobabilitytheory.Forexample,toupdateastateofknowledgeaboutsomefutureeventFEconditionedonsomeobserveddataD

andinvolvingmodelsassigningnumericalvaluesMkPredictingFutureEventsinCATheinferentialapproachprovidesaquantitativewayfortheinformationprocessortoupdateitsstateofknowledgeaboutthecolorofanycellinthecellularautomaton.Here,wehavelostinformationaboutwhichmodel(rule)isgoverningtheevolutionoftheCA.Wemustaverageoverthepredictionsmadeby256modelsPredictingManyCellsoftheCAJointprobabilitytableisimpossiblyhuge!(Andanysummationishardtoo!)ThepredictionformulaforupdatingarbitrarilymanycellsoftheCA.AnyExistingSolutions?

Wehavetomakethedifficulttransitionfrommicro-eventstomacro-eventsintryingtopredictthefarfutureforCA.Historically,StatisticalPhysicsfacedthesameproblem.Macro-StatementsArePredictedbyInferentialApproach*SeeJaynes,Chapter18,fordiscussion.Macro-Statementsintheformoffuturefrequencycountscanbepredictedconditionedonpastfrequencycounts.*UsefulforCA?ThesameanalyticalapparatuscouldbeappliedtopredictfrequencycountsofblackandwhitecellsforeachofncellsatsomefutureMthtimestep.Butisthistypeofmacro-statementoneWolframwouldacceptasmeaningful?(Whathasbeenvoluntarilydiscardedmightbeviewedasveryimportant!)CanTechniquesfromInformationGeometryHelp?UseconceptsfromInformationGeometry.

Try

a-projectionfromcomplicatedprobabilitydistributionatpointPingeneralmanifoldtocomputationallytractabledistributionatpointQwithinsub-manifold.(Amari)MaximumEntropyPrinciplewithmeasurefunctionm(x)(Jaynes)MeanFieldApproximationinStatisticalPhysicsBeliefPropagationalgorithmsSinequanonofpredictingInordertopredict,micro-informationmustbevoluntarilydiscarded!ImplicationsforCAWhatkindofmicro-informationshouldbediscarded?Whatkindofmacro-statementsmakesenseforCA?MyMainArgumentWolframispessimisticaboutbeingabletopredictthebehaviourof

deductivesystems

likecellularautomataintothefarfuture.

Heiscorrect.However,(followingJaynes)ifCAaretreatedfromtheperspectiveof

inferenceandinformation,

thenalimitedformofpredictionbecomespossible.Thismeansthatwemustemploy

probabilitytheoryasthegeneralizationofclassicallogic,

thatis,weuseinferenceinsteadofdeduction.It’sarepetitionoftheold

analogyfromstatisticalmechanics.Wevoluntarilygiveupinformationaboutthemicrodetailsofmoleculardynamicsinexchangefortheabilitytopredictmacrovariables.Themoral:WeMUSTapproachtheproblemof

predictingtheconsequencesofanysufficientlydetailedexplanatorymodeloftheworld

throughinferenceandinformation.SummaryofTechnicalPointsBooleanfunctionsf(x1,x2,…xn)=f:Bn

Bforanynumberofvariables.Abstract,general,closed,donotinvolvenumbersorarithmeticoperations,andareeasytocomprehend.Talkfocusedonn=2(CL)andn=3(CA).Perfectfoilforprobabilitytheory’sformalmanipulationrules.SummaryofTechnicalPointsAnysuchBooleanfunctioncanbeexpandedintotheDisjunctiveNormalForm.AclassicallogicfunctionisaBooleanfunctionandcanbeexpressedviatheDNF.Logicproblems(classicalsyllogisms)canbesolvedbyprobabilitytheory.Jointprobabilitytablesillustratehowsomemodela