Causal Combinatorics

QC 2023-05-22

Abstract

Att förklara data på ett kortfattat och effektivt sätt har blivit allt viktigare i dagens samhälle. Den här avhandlnigen behandlar frågan om att upptäcka orsakssamband i data och hur detta kan göras från ett matematiskt perspektiv. Att använda ramverket av grafiska modeller har flera fördelar, från tolkningsbarhet till effektivitet. En av de vanligaste grafiska modellerna är riktade acykliska grafer (DAG:er), som har använts för att modellera komplexa problem inom en mängd olika områden.Vanligtvis kommer modellen från antaganden, eller från experiment, vilka båda är metoder med olika nackdelar. Att härleda en DAG från endast data är dock en svår uppgift och en central fråga inom kausal bestämmning. På grund av den kombinatoriska explosionen av antalet DAG:er kan vi inte göra detta för hand och därför behöver vi utforma algoritmer specifikt för denna uppgift; flera algoritmer finns redan inom detta område: PC, GES, MMHC och Greedy SP, för att nämna några. Studený föreslog en alternativ infallsvinkel med hjälp av heltalsvärda multimängd-funktioner (imset).Detta i sin tur möjligör det att se DAG-upptäckt som ett linjärt optimeringsproblem.Mer specifikt studerar vi den karakteristiska imset-polytopen, $\CIM_n$, vars hörn motsvarar Markov-ekvivalensklasser av DAG:er.En central fråga i den här avhandlingen är att förstå dess kanter och hur detta kan användas i algoritmer. 

Många av de bäst presterande algoritmerna använder en fast uppsättning drag för att girigt omvandla en DAG till en annan och optimera en målfunktion. I den här avhandlingen visar vi att de mest använda dragen har en polyhedral tolkning som en kantvandring längs $\CIM_n$, vilket ger oss ett geometrisk perspektiv på dessa algoritmer. Detta gör det i sin tur möjligt för oss att utforma algoritmer som generaliserar tidigare algoritmer och diskutera hur vissa sidor på $\CIM_n$ kan användas för att förbättra de bästa algoritmerna. Specifikt är sidorna på $\CIM_n$ med tydlig grafisk tolkning av särskild betydelse, till exempel $\CIM_G$, det konvexa höljet för alla imsets som kodar för DAG:er med ett givet skelett $G$. Genom att introducera en algoritm skeletal greedy CIM, som testar efter betingat oberoende för att hitta $G$, och sedan fortsätter på ett girigt sätt, visar vi att dessa inte bara är intressanta från en teoretisk synvinkel, utan likaså är direkt tillämpbara på verkliga data.

I allmänhet är väldigt lite känt om kantstrukturen för $\CIM_n$, framförallt i termer av graferna. Om vi däremot antar att $G$ är ett träd kan vi ge en fullstäding beskrivning av kanterna för $\CIM_G$. Detta tillåter oss att beskriva kopplingar till flera andra välkända polytoper. Dessutom generaliserar detta algoritmen skeletal greedy CIM, och ger oss en hybridalgoritm för att upptäcka riktade träd.  De extra kanterna, eller dragen, visar sig vara speciellt användbara när vi har väldigt lite data. 

Ett viktigt mått på komplexiteten hos en kantvandring är diametern av en polytop. Vi visar att diametern av de tidigare nämnda polytoperna är polynomiskt begränsade, med låg grad, i antalet noder i DAG:erna. Detta är förvånande då dimensionen växer exponentiellt. 

En sista metod vi använder för att förstå kantstukturen av karakteristika imset-polytoper är att definiera rombuskriteriet. Det är ett enkelt tillräckligt villkor för att avgöra om två hörn inte bildar en kant. För flertalet karakteristiska imset-polytoper är rombuskriteriet tillräckligt och nödvändigt villkor och ger således den kompletta kantstrukturen. Därför lyfter vi frågan för vilka karakteristiska imsetpolytoper det är sant. Vi visar att nästan alla par av hörn av den kordala grafpolytopen uppfyller rombuskriteriet och förmodar att det håller för varje par. Genom att använda detta kriterium tillhandahåller vi också ett sätt för att beräkna kantstrukturen för vissa 0/1-polytoper som skalar bättre med dimension. Således kan vi beräkningsmässigt visa att rombuskriteriet beskriver kantstrukturen för $CIM_n$ när $n\leq 5$ och kantstrukturen för den kordala grafpolytopen när $n \leq 6$.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-327056