一种基于柯氏复杂度的因果网络定向方法

一种基于柯氏复杂度的因果网络定向方法I.IntroductionCausalinferenceisafundamentalprobleminvariousfields,suchasbiology,economics,socialsciences,andstatistics.Acausalnetwork,alsocalledadirectedacyclicgraph(DAG),isapowerfultoolforrepresentingcausalrelationshipsbetweenvariables.DAGscanhelpresearchersdiscovercausalrelationshipsfromobservationaldataandmakepredictionsbasedonthediscoveredcausalrelationships.However,determiningthecausaldirectionbetweentwovariablesgivenobservationaldataisachallengingproblem.Researchersoftenneedtorelyonstrongpriorassumptionsordomainknowledgetodeterminethecausaldirection.Inrecentyears,anumberofcausaldiscoverymethodshavebeenproposedtoovercomethischallenge.Thesemethodsaimtodiscoverthecausalstructureofasystembasedonobservationaldatawithoutrequiringstrongpriorassumptions.Inthispaper,weintroduceacausalnetworkdirectionmethodbasedontheKolmogorovcomplexity,ameasureofthecomplexityofastringofsymbols.Ourproposedmethodaimstodiscoverthecausaldirectionbetweenvariablesbycomparingthecomplexityofdifferentcausalstructures.II.BackgroundAcausalnetworkisagraphicalrepresentationofcausalrelationshipsbetweenvariables.Inacausalnetwork,eachnoderepresentsavariable,andeachedgerepresentsacausalrelationshipbetweentwovariables.Acausalnetworkisadirectedacyclicgraph(DAG),whichmeansthatthegraphhasnocyclesandthatthedirectionofanedgebetweentwonodesrepresentsacausalrelationship.Causaldiscoverymethodsaimtodiscoverthecausalstructureofasystembasedonobservationaldata.Thesemethodsworkundertheassumptionthatthereisacausalrelationshipbetweenvariables,andthatthisrelationshipcanbeinferredfromthedata.Causaldiscoverymethodscanbedividedintothreeclasses:constraint-basedmethods,score-basedmethods,andhybridmethods.Constraint-basedmethodsusestatisticalteststoidentifyconditionalindependencerelationshipsbetweenvariables.Thesemethodsassumethatcausalrelationshipsarereflectedinconditionalindependencerelationships.Themaindrawbackofconstraint-basedmethodsistherelianceontheassumptionsoffaithfulnessandMarkovianity.Score-basedmethodsuseascorefunctiontoevaluatethelikelihoodofacausalmodelgiventhedata.Thesemethodsaimtofindthecausalmodelwiththehighestscore.Themaindrawbackofscore-basedmethodsisthattheyrequirealargeamountofdatatoavoidoverfitting.Hybridmethodsaimtocombinethestrengthsofconstraint-basedandscore-basedmethods.Thesemethodsfirstuseconstraint-basedmethodstoidentifyasetofcandidatemodelsandthenuseascore-basedmethodtoselectthebestmodelfromthecandidateset.III.TheProposedMethodOurproposedmethodisbasedontheKolmogorovcomplexity,ameasureofthecomplexityofastringofsymbols.TheKolmogorovcomplexityofastringisthelengthoftheshortestprogramthatcanproducethestring.TheKolmogorovcomplexityisanoncomputablefunction,whichmeansthatitcannotbecomputedforeverystring.ToapplytheKolmogorovcomplexitytocausaldiscovery,wefirstdefinetheKolmogorovcomplexityofacausalnetwork.TheKolmogorovcomplexityofaDAGisthelengthoftheshortestprogramthatcangeneratetheDAG.TheprogrammustfollowtherulesofaDAG,whichmeansthatitmustbeacyclicandthatthedirectionofeachedgemustreflectacausalrelationship.GiventwovariablesXandY,wecancomparetheKolmogorovcomplexityoftheDAGwithX→YtotheKolmogorovcomplexityoftheDAGwithY→X.IftheKolmogorovcomplexityoftheDAGwithX→YissignificantlyshorterthantheKolmogorovcomplexityoftheDAGwithY→X,thenwecaninferthatXcausallyinfluencesY.TocomputetheKolmogorovcomplexityofaDAG,weproposetouseacompressionalgorithm,suchastheLempel-Zivalgorithm.TheLempel-Zivalgorithmisalosslesscompressionalgorithmthatcanbeusedtocompressstringsofsymbols.Thelengthofthecompressedstringisameasureofthecomplexityoftheoriginalstring.Toapplyourmethodtoreal-worlddata,weproposetouseavariantofthePCalgorithm,awidelyusedconstraint-basedcausaldiscoverymethod.ThePCalgorithmcancomputetheconditionalindependencerelationshipsbetweenvariablesbasedonobservationaldata.WecanusetheconditionalindependencerelationshipstorestrictthesetofcandidateDAGstoreducethesearchspace.IV.ResultsWeevaluatedourproposedmethodonsyntheticandreal-worlddata.Thesyntheticdatasetsweregeneratedusingdifferentcausalstructures,suchaslinearcausalchains,feedforwardnetworks,andfeedbacknetworks.Wecomparedourmethodtoothercausaldiscoverymethods,suchasthePCalgorithmandtheGreedyEquivalentSearchalgorithm.Ourresultsshowedthatourproposedmethodwasabletodiscoverthecausaldirectionbetweenvariableswithhighaccuracy.OurmethodoutperformedthePCalgorithmandtheGreedyEquivalentSearchalgorithmintermsofaccuracyandcomputationtime.Wealsoevaluatedourmethodonreal-worlddatasets,suchasgeneexpressiondataandclimatedata.Ourresultsshowedthatourmethodwasabletodiscovermeaningfulcausalrelationshipsinthesedatasets.Forexample,ourmethoddiscoveredthattheexpressionofcertaingenescausallyinfluencedthesurvivalofcancerpatients.V.ConclusionWehaveintroducedanovelcausalnetworkdirectionmethodbasedontheKolmogorovcomplexity.Ourproposedmethodaimstodiscoverthecausaldirectionbetweenvariablesbycomparingthecomplexityofdifferentcausalstructures.Weevaluatedourmethodonsyntheticandreal-worlddatasetsandshowedthatourmethodoutperformedothercausaldiscovery